走楼梯——二维走楼梯（三）

LeetCode_62_UniquePaths

题目分析：

状态转换方程
  dp[i][j] = dp[i-1][j] + dp[i][j-1] (dp[i][j]代表有多少种方法可到达第i行j列)
递推初始项
  dp[i][0] = dp[0][j] = 1
  
dp数组需要将第一行第一列初始化为1
若m = 4 ， n = 3
{{1, 1, 1},
 {1, 0, 0},
 {1, 0, 0},
 {1, 0, 0}}
 
可选择横向 OR 纵向扫描 （根据题意，无论横纵，从左到右，从上到下不变）

递推初始项的形成 这里选择横向扫描
1.为什么是第一行第一列
  横向扫描，也是一行一行地，从左到右地递推过程。
  根据状态转换方程，dp[i][j]需要其上方的dp[i-1][j]和左方的dp[i][j-1]即可得到值。
  每行遍历都需要上一行的数据
  那么必然从第二行开始遍历，第一行就需要初始化。
  每行遍历都需要最左边的第一个值
  那么必然从第二列开始遍历，第一列就需要初始化。
2.值的选取
  根据递推式推出来的
  先看行，第一行上面没有行，自然只能从自身的左方推过来。
  也就是dp[i][j] = dp[i-1][j] + dp[i][j-1]这个式子中
  去掉了上方的dp[i-1][j]，只剩下左方的dp[i][j-1]，显然dp[0][0] = 1即可挨个推出。
  列同理。
  当然也可以根据题意，一眼看出到达第一行第一列的各个位置，有且只有只有1种走法，
  但是这样没有普适性，比如下一题就没那么容易看出来了。

不再啰嗦写递归形式，只需要知道是可以写的就好。

解法一：循环-动态规划

public static int uniquePaths_dp_loop(int m, int n) {
    int [][]dp = new int[m][n];

    Arrays.fill(dp[0], 1);
    for (int i = 1; i < m; i++) {
        dp[i][0] = 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];
}

解法二：循环-动态规划-内存优化

public static int uniquePaths_dp_loop_lessMemory(int m, int n) {
    int []dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j-1];
        }
    }
    return dp[n-1];
}

解法二分析

选用横向扫描
每“格”的值只需要 上方 和 左方 的值
--> 每“行”的值只需要前一行 和 当前行第一列
1.前一行：已经存在于dp[]中 因为是上一轮的结果 dp[]第一轮初始化为1
2.当前行第一列：由于从1开始遍历dp[0]永远等于1
--> dp[j] = dp[j] + dp[j-1]; --- 此刻等号右边dp[j]代表上方，dp[j-1]代表左方
--> dp[j] += dp[j-1];
PS:这里每轮的第一列并没有用状态方程来推，因为是不变的1，下一题将看到第一列的更新的写法。

解法三：循环-动态规划-更进一步内存优化

public static int uniquePaths_dp_loop_bestMemory(int m, int n) {
    if(m > n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }else{
        int[] dp = new int[m];
        Arrays.fill(dp, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[m - 1];
    }
}

解法三分析

根据m和n的大小来决定是横向还是纵向扫描，可更加节约内存。

总结

套路就是这么明显，只是二维情况下多了一个根据行列大小来优化内存的情况。

相应例题的 Github