动态规划A计数问题

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

开始吧！

62. 不同路径

题目地址

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

示例1： >输入: m = 3, n = 2
>输出: 3
>解释:从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例2： >输入: m = 7, n = 3
>输出: 28

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * \(10 ^ 9\)

begin

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

动态规划

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

一、确定状态

1. 最后一步
2. 子问题

二、转移方程

三、初始条件和边界问题

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

四、计算顺序

A计数问题

很明显这是一个关于计数的问题，题目要求解的是机器人有多少种方案走到右下角，而不是要求这些方案里是怎样走到右下角的，这就是动态规划的一个标志吧，不要过程要结果。

按照上面的顺序来：

一、确定状态

1. 最后一步

我们假设机器人走了最后一步到达终点，也只有两种可能，从上方向下走，从左方向右走。即从(m-2,n-1)或(m-1,n-2)走到了终点(m-1,n-1)。

2. 子问题

根据最后一步，我们把终点换了个位置，即上方的(m-2,n-1)和(m-1,n-2)，并且到这两点之和作为结果。很明显是将一个大问题变成一个规模更小的问题了，所以这个就是子问题。

二、转移方程

f[i][j]=f[i-1][j]+f[i][j-1]。

三、初始条件和边界问题

出发点f[0][0]=1，最上一层和最左一层都是只有一条路。

四、计算顺序

二维数组更注重顺序，要清楚我们要求的所有条件都在上一步求出了。

一种java题解

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i==0||j==0){
                    dp[i][j]=1;
                }else{
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[n-1][m-1];
    }
}

应该都能看懂吧。

详细题解

推荐视频

动态规划入门