• 动规五部曲
  • dp数组含义：到达到第i行，第j列的所有不同种走法，即有多少条路径可到达
  • 递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  • dp数组初始化，要初始化最上面一行，与最左边一列的值，都为1，00位置也是1，也可以是0，因为这个点的值对计算毫无影响
  • 遍历顺序：从左往右，从上向下
  • 打印

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

• 汇总