有一排台阶，每个台阶上有一个非负整数，代表在该台阶上时能最多

public class Item05 {

	public static boolean flag = false;	//标志位

	/**
	 * 递归实现
	 * @param array	台阶数组
	 * @param position	当前台阶位置
	 */
	public static void jump(int[] array, int position) {
		int steps = array[position];		//可以到达的台阶数
		
		//从1到step循环，i为跳的阶数
		for (int i = 1; i <= steps; i++) {
			if (position + i == array.length - 1){
				flag = true;
				return ;
			}else
				jump(array, position + i);
		}
	}

	public static void main(String[] args) {
		int[] arrays = { 2, 1, 3, 1, 1, 0 };
		jump(arrays, 0);
		System.out.println(flag);
	}
}

def canJump(self, nums):
        maxStep=nums[0]
        for i in range(1,len(nums)):
            if maxStep==0:
                return False
            maxStep-=1
            if maxStep<nums[i]:
                maxStep=nums[i]
        return True

// 从后向前   逐个判断     用到标志位   【比较好理解】
#include <iostream>
using namespace std;
#include <vector>


bool jump(int array[], int size)
{       bool can = false;           
    vector<bool> is(size, false);
    is[size - 1] = true;
    for (int i = size - 2; i >= 0; i--)
    {
        for (int j =1; j <= array[i]; j++)
        {
            if (i + j <= size - 1)
            {
                if (is[i + j] == true)
                {
                    is[i] = true;
                    break;
                }
            }

        }

        if (i == 0 && is[i] == true)
        {
            can = true;
        }

    }

    return can;
}

void test_jump()
{
    int arr1[6] = {4 ,2, 2 ,1, 0, 2};
    int arr2[6] = {2 ,1 ,3 ,1 ,1 ,0};
    cout<<jump(arr1,6)<<endl;
    cout<<jump(arr2,6)<<endl;
}



int main()
{
    test_jump();
    return 0;
}

//时间复杂度: o(n)~o(n^2)
//空间复杂度：o(n);
#include<stdio.h>
#include<malloc.h>
int jump(int arr[], int size)
{
	int *p_flag = NULL;
	int i, j;
	if (NULL == arr || 0 >= size)
		return 0;
	else if (1 == size)
		return 1;
	p_flag = (int*)malloc(sizeof(int)*size);	//对应第i个台阶的flag,若为1则表示可以到达，0则不可以
	memset(p_flag, 0, sizeof(int)*size);
	if (arr[0] <= 0)
		return 0;
	for (i = 1; i <= arr[0]; i++)
		p_flag[i] = 1;
	for (i = 1; i < size; i++)
	{
		//台阶从第1个开始，如果当前这个台阶i可以到达，当前台阶最大可向前走arr[i]步，
		//置标志位，使台阶第 i+1 到 i + arr[i] 台阶标志位都为1；
		if (1 == p_flag[i])
		{
			// 注意条件 i + j < size 避免溢出 
			for (j = 1; j <= arr[i] && i + j < size; j++)
			{
				p_flag[i + j] = 1;
			}
			//可能存在中间第i个台阶就可以直接跳arr[i]步，直接到最后一个台阶，此时可提前结束判断。
			if (1 == p_flag[size - 1])
				return 1;
		}
	}
	return p_flag[size - 1];//返回最后一个台阶标志
}
int main()
{
	int arr[2][20] = { { 4, 2, 2, 1, 0, 2 } ,
						{ 2, 1, 3, 1, 1, 0 } };
	printf("arr0: %d\n", jump(&arr[0][0], 6));
	printf("arr1: %d\n", jump(&arr[1][0], 6));
	return 0;
}

这道题我考虑用递归的方法解题。 package zhang;

//4 2 2 1 0 2 返回 false
//2 1 3 1 1 0 返回 true
public class Step {
	private boolean flag=false;//设置标志位
	public static void main(String[] args)
	{
		int [] ladder={2,1,3,1,1,0};
		Step step=new Step();
		step.stepLadder(ladder, 0);
		if(step.flag)
			System.out.println("可以到达！");
		else
			System.out.println("无法到达！");
		
	}
	public void stepLadder(int [] ladder,int start)
	{
		int i;
		for(i=start;i<=ladder.length-1;i++)
		{
			if((ladder[start]==0)||(start+ladder[start]>ladder.length-1))
				break;
			if(start+ladder[start]==ladder.length-1)
				flag=true;
			else
				stepLadder(ladder,start+ladder[start]);
		}
	}
}从数组第一个开始跳，下次跳的位置为本次的开始位置加上跳的步数（题目只是说了最大步数，不一定非得跳最大步数）start+ladder[start],那么从ladder[start]往后的数组又是一个跳台阶问题，可以考虑用递归

bool jump(int a[], int n)
{
	int j;
	vector<int>b(n,0);
	b[0] = 1;
	for (int i = 0; i < n; i++)
	{
		for (j = 0; j < i; j++)
		{
			if (a[j] >= i - j&&b[j]==1)
				b[i]=1;
		}
	}
	if (b[n - 1] == 1)
		return true;
	return false;
}

static boolean jump(int array[], int size) {
    boolean []boolArr = new boolean[size];
    return isJump(array, boolArr, 0, size);
}

private static boolean isJump(int[] arr, boolean[] boolArr, int i, int size) {
    // TODO Auto-generated method stub
    if (i == size - 1)
        return true;
    if (arr[i] == 0) {
        boolArr[i] = false;
    }
    boolean isNextStepOk = isJump(arr, boolArr, i + 1, size);
    if (isNextStepOk) {
        boolArr[i] = true;
    }
    if ((isNextStepOk && arr[i] > 0 ) || size - i - 1 <= arr[i])
        return true;
    for (int k = i + 2; k < i + arr[i]; k++) {
        if (boolArr[k] == true)return true;
    }
    return false;
}

public class CanReachTop {
    private boolean canReach(int i, boolean[][] w) {
        if (i == 0)
            return true;
        boolean rst = false;
        for (int j = 0; j < i; j++) {
            rst = rst || w[j][i];
        }
        return rst;
    }

    public boolean jump(int array[], int size) {
        int n = array.length;
        boolean[][] w = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (canReach(i, w)) {
                    if (j - i <= array[i]) {
                        w[i][j] = true;
                        if (j == n - 1)
                            return true;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        CanReachTop canReachTop = new CanReachTop();
        int[] a = {4, 2, 2, 1, 0, 2};
        System.out.println(canReachTop.jump(a, 3));
    }
}

bool jump(int array[], int size)
{
    if(array == NULL || size <= 0)
    {
        cout<<"输入有误..."<<endl;
        return false;
    }
    bool isLastOne = false;
    int i=0;
    while(i < size-1)
    {
        if(array[i] == 0)
        {
            isLastOne = false;
            break;
        }
        i += array[i];
    }
    if( i == size-1)
        isLastOne=true;
    return isLastOne;
}

bool jump(int array[], int size)
{
    for(int i=0; i<size-1; i++)
    {
        if(array[i]==0) return false;
        i += array[i];
    }
    return true;
}