动态规划特辑-01

三、计数型动态规划——机器人路径问题

1、题目描述

2、步骤一：确定状态

①最后一步

②子问题

3、步骤二：转移方程

4、步骤三：初始条件和边界情况

5、步骤四：计算顺序

如何确定计算顺序呢？根据转移方程来，在算右下角的格子时候，左面的格子刚刚算得到，上面的格子已经得到。

6、题目练习——lintcode-114.不同的路径

①问题描述

②代码解决

• 这里把初始化放到了for循环里面，为什么不在外面写呢？因为for循环会把所有格子都遍历一遍，所以直接写到里面就好了。

public class Solution {
    /**
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    public int uniquePaths(int m, int n) {
        //注意此处为什么之开辟m到n，因为最终的结果只用到[m-1,n-1]
        int[][] f = new int[m][n];
        int i,j;
        for (i=0;i<;m;i++){//row: top to bottom
            for(j=0;j<n;j++){//column: left to right
                if(i==0 || j==0){
                    f[i][j] = 1;
                }else{
                    f[i][j] = f[i-1][j] + f[i][j-1];
                }
            }
        
        }
    return f[m-1][n-1];
    }
}

四、存在型可行性型动态规划——Jump Game

1、题目描述

2、步骤一：确定状态

①最后一步

通过最后一步来确定子问题

②子问题

3、步骤二：转移方程

4、步骤三：初始条件和边界情况

5、步骤四：计算顺序

6、题目练习——lintcode-116.跳跃游戏

①问题描述

@H_961_304@

②代码解决

public class Solution {
    /**
     * @param A: A list of integers
     * @return: A boolean
     */
    public boolean canJump(int[] A) {
        int n = A.length;
        boolean[] f = new boolean[n];
        f[0] = true;//initialization

        for (int j=1;j < n;j++){
            f[j] = false; //假设不能通过
            //previous stone i
            //last jump is From i to j
            for (int i=0; i < j; i++){
                if(f[i] &amp;& i + A[i] >= j){
                    f[j] = true;
                    break;
                }
            }
        }
        return f[n-1];
    }
}

五、后续学习方向

脚本宝典总结

以上是脚本宝典为你收集整理的动态规划特辑-01-基础篇全部内容，希望文章能够帮你解决动态规划特辑-01-基础篇所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。