leetcode 62. 不同路径

2023.8.8

        用dp算法一遍过了，很舒服。 重点还是要确定dp数组的含义，本题的dp数组要设成二维的，dp[i][j]的含义是：到（i，j）这个点一共有多少种路径。由于题中说了m和n都大于1，所以假设一种极端情况 ，n和m都等于1时，此时路径应该是1的，我根据推导画出以下草图：

         每个方格的数字代表到当前位置的路径个数。首先，第一行和第一列肯定都是1，因为机器人只能向右或者向下走。从第二行第二列开始，可以发现当前位置的路径个数 = 上方位置的路径个数+左边位置的路径个数。 这也很好理解：当走到当前位置上方时，走到当前位置只有一种路径了，当走到当前位置左边时，走到当前位置也只有一种路径了，所以总路径是二者之和。这种递推方式有点像前几天爬楼梯那题，只不过本题是二维的形式。于是递推公式也推导出来了，            即 dp[i][j] = dp[i-1][j] + dp[i][j-1];    

        然后由于需要从第二行第二列开始遍历，需要判断一下当n=1或者m=1的情况：此时只有一种路径，所以直接返回1。 然后两个for循环都从索引1开始遍历：不断向右向下递推赋值。具体代码还是很简单的：

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