9.24 动态规划---路径问题

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

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

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

思路一：排列组合

因为机器到底右下角，向下几步，向右几步都是固定的，

比如，m=3, n=2，我们只要向下 1 步，向右 2 步就一定能到达终点。

直接计算C(m+n-2,m-1)即可。时间复杂度为O(n)，空间复杂度O(1)

思路二：动态规划

1、确定状态方程

dp[i][j]表示从头开始到i、j的路径数。

2、确定状态转移方程

因为想要到达i,j其实只有两个方向，一个是从上方，一个是从左方，即i-1和j-1，两个方向的和即为目前的路径数。dp[i][j] = dp[i-1][j] + dp[i][j-1]

3、确认边界条件

需要注意边界值，当i、j到达0的时候，即为到达边界，也就只有一个方向，返回1

注意：题目中的 n 是行row，而 m 才是列column。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(n,vector<int>(m,0));
        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];
    }
};