题解 | #不同路径的数目（一）#

数学解法不是很理解，能够画出来式子，但是转化为代码计算不是很理解

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
  //  到达最后一个结点有两种方式，一个向下一个向右这两种
  //  使用递归从后面往前推容易理解
  //  使用动态规划
  //  运用数学 --> 最优解
    int uniquePaths(int m, int n) {
//  递归思路
      if (m == 1 || n == 1) {
        return 1;
      }
      
      //  分别是开头向右走和向下走的结果之和
      return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);

//  动态规划
      //  dp[m][n] 表示在m*n地图中的路径数，求值范围从 1，1 到 m，n
      std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
      
      for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
          //  两个if都是边界处，不能用转移方程
          //  同时也可以直接求得，无需状态转移
          if (i == 1) {
            dp[i][j] = 1;
            continue;
          }
          if (j == 1) {
            dp[i][j] = 1;
            continue;
          }
          //  每一结点的路径数都等于其左方和上方结点路径数之和
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
      }
      
      return dp[m][n];
//  运用数学
      //  m-1 和 n-1 总步数，对这些总步数进行排列组合。
      //  手动计算出结果表达式，然后算表达式结果
      //  (m+n-2)!/((m-1)!*(n-1)!)
      //防止溢出
      long res = 1; 
      for(int i = 1; i < n; i++)
          res = res * (m + i - 1) / i; 
      return (int)res;
    }
};