image.png

    状态定义：dp[i][j] 表示到达 （i，j）处的不同路径总数

    问题目标：dp[n][m]

    状态转移：由于每次只能往右或往下移动，那么 dp[i][j] 必然与 dp[i-1][j] （注：（i-1，j）往下走一步到（i，j)) 和 dp[i][j - 1]有关，又由于题目求的是不同路径的总数，那么自然有 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

    状态初始化：dp[1][1] = 1，且 dp 中第一行、第一列均为1.

    时间复杂度：O(m * n)

    空间复杂度：O(m * n)

    1. class Solution {
    2.     public int uniquePaths(int m, int n) {
    3.         int[][] dp = new int[m + 1][n + 1];
    5.         for(int i = 1; i <= n; i++){
    6.             dp[1][i] = 1;
    7.         }
    8.         for(int i = 1; i <= m; i++){
    9.             dp[i][1] = 1;
    10.         }
    11.         for(int i = 2; i <= m; i++){
    12.             for(int j = 2; j <= n; j++){
    13.                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
    14.             }
    15.         }
    16.         return dp[m][n];
    17.     }
    18. }