动态规划C可行性问题

接下来用一道例题来认识动态规划的可行性问题，首先声明一下，这些题可能有其他解法，但在这里我只是说一说关于动态规划的解法。

开始吧！

55. 跳跃游戏

题目地址

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例1： >输入: [2,3,1,1,4]
>输出: true
>解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例2： >输入: [3,2,1,0,4]
>输出: false
>解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

begin

题目描述得很清楚了，你是否有了想法，建议先尝试一下，考虑用动态规划怎么解。

动态规划

A 计数问题 B 最值问题 C 可行性问题

一、确定状态

1. 最后一步
2. 子问题

二、转移方程

三、初始条件和边界问题

初始条件：用转移方程算不出来，需要手工定义
边界情况：数组不能越界

四、计算顺序

C可行性问题

很明显这是一个关于可行性的问题，题目要求解的是能否到达最后的位置。题目让求的仅仅是true或是false，这就是动态规划的一个标志吧，不要过程要结果。

按照上面的顺序来：

一、确定状态

1. 最后一步

我们假设有这么一块位置使我们跳到了最后一个位置。

2. 子问题

根据最后一步，我们把由起点能否跳到最后一个位置的问题变成了能否跳到它前一个的位置（能从这跳到终点），很明显是将一个大问题变成一个规模更小的问题了，所以这个就是子问题。

二、转移方程

f[j]表示能跳到j，f[j]=OR(0<=i<j)(f[i] AND i+a[i]>=j)。

三、初始条件和边界问题

出发点f[0]=true，其它认真考虑考虑，不要出现大错误。

四、计算顺序

关于这个题的计算顺序还是比较清晰的，我们从出发点算到终点即可，需要注意若可到达即退出，因为这是OR或问题，最后得到f(n)。

一种java题解

class Solution {
    public boolean canJump(int[] nums) {
        int n=nums.length;
        boolean[] f=new boolean[n];
        f[0]=true;
        for(int i=1;i<n;i++){
            f[i]=false;
            for(int j=0;j<i;j++){
                if(f[j]&&nums[j]+j>=i){
                    f[i]=true;
                    break;
                }
            }
        }
        return f[n-1];
    }
}

注意这个题用动态规划并不是最优解，贪心算法更优一些，可以了解一下，下面给出代码了，思考思考。

class Solution {
    public boolean canJump(int[] nums) {
        int maxjump=0;
        for(int i=0;i<nums.length&&i<=maxjump;i++){
            maxjump=Math.max(maxjump,i+nums[i]);
            if(maxjump>=nums.length-1){
                return true;
            }
        }
        return false;
    }
}

详细题解

推荐视频

动态规划入门