1
2

输入：m = 3, n = 7
输出：28

1
2
3
4
5
6
7

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

1
2

输入：m = 7, n = 3
输出：28

1
2

输入：m = 3, n = 3
输出：6

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 动态规划
    /// 1. 设dp[m][n]: mxn格的不同路径数
    /// 1. 递推关系: dp[i][j] = dp[i-1][j] + dp[i][j-1]
    /// 2. 初始条件: dp[i][0] = dp[0][j] = 1
    /// 3. 结果: dp[m-1][n-1]
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        let (m, n) = (m as usize, n as usize);
        let mut dp = vec![vec![1; n]; m];
        for i in 1..m {
            for j in 1..n {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }

        dp[m - 1][n - 1]
    }
}
// @lc code=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    /*
    ## 解题思路
    * 动态规划
    f(m,n): 代表走到(m,n)这个方格的步数；
    走到(m,n)方格有两种走法：
        1. 先走到(m-1,n)方格处，再往下走一格；
        2. 先走到(m,n-1)方格处，再往右走一格；
    递推公式：f(m,n) = f(m-1, n) + f(m, n-1)
    初始条件: 
            f(i,0) = 1
            f(0,j) = 1
    */
    int uniquePaths(int m, int n) {
        vector<vector<int>> f(m, vector<int>(n, 1));
        for(int i=1; i<m; i++) {
            for(int j=1; j<n; j++) {
                f[i][j]=f[i-1][j]+f[i][j-1];
            }
        }
        return f[m-1][n-1];
    }
};