LeetCode_62_UniquePaths

題目分析：

狀態(tài)轉(zhuǎn)換方程
  dp[i][j] = dp[i-1][j] + dp[i][j-1] (dp[i][j]代表有多少種方法可到達(dá)第i行j列)
遞推初始項(xiàng)
  dp[i][0] = dp[0][j] = 1
  
dp數(shù)組需要將第一行第一列初始化為1
若m = 4 ， n = 3
{{1, 1, 1},
 {1, 0, 0},
 {1, 0, 0},
 {1, 0, 0}}
 
可選擇橫向 OR 縱向掃描 （根據(jù)題意，無(wú)論橫縱，從左到右，從上到下不變）

遞推初始項(xiàng)的形成 這里選擇橫向掃描
1.為什么是第一行第一列
  橫向掃描，也是一行一行地，從左到右地遞推過(guò)程。
  根據(jù)狀態(tài)轉(zhuǎn)換方程，dp[i][j]需要其上方的dp[i-1][j]和左方的dp[i][j-1]即可得到值。
  每行遍歷都需要上一行的數(shù)據(jù)
  那么必然從第二行開(kāi)始遍歷，第一行就需要初始化。
  每行遍歷都需要最左邊的第一個(gè)值
  那么必然從第二列開(kāi)始遍歷，第一列就需要初始化。
2.值的選取
  根據(jù)遞推式推出來(lái)的
  先看行，第一行上面沒(méi)有行，自然只能從自身的左方推過(guò)來(lái)。
  也就是dp[i][j] = dp[i-1][j] + dp[i][j-1]這個(gè)式子中
  去掉了上方的dp[i-1][j]，只剩下左方的dp[i][j-1]，顯然dp[0][0] = 1即可挨個(gè)推出。
  列同理。
  當(dāng)然也可以根據(jù)題意，一眼看出到達(dá)第一行第一列的各個(gè)位置，有且只有只有1種走法，
  但是這樣沒(méi)有普適性，比如下一題就沒(méi)那么容易看出來(lái)了。

不再啰嗦寫(xiě)遞歸形式，只需要知道是可以寫(xiě)的就好。

解法一：循環(huán)-動(dòng)態(tài)規(guī)劃

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];
}

解法二：循環(huán)-動(dòng)態(tài)規(guī)劃-內(nèi)存優(yōu)化

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];
}

解法二分析

選用橫向掃描
每“格”的值只需要 上方 和 左方 的值
--> 每“行”的值只需要前一行 和 當(dāng)前行第一列
1.前一行：已經(jīng)存在于dp[]中 因?yàn)槭巧弦惠喌慕Y(jié)果 dp[]第一輪初始化為1
2.當(dāng)前行第一列：由于從1開(kāi)始遍歷dp[0]永遠(yuǎn)等于1
--> dp[j] = dp[j] + dp[j-1]; --- 此刻等號(hào)右邊dp[j]代表上方，dp[j-1]代表左方
--> dp[j] += dp[j-1];
PS:這里每輪的第一列并沒(méi)有用狀態(tài)方程來(lái)推，因?yàn)槭遣蛔兊?，下一題將看到第一列的更新的寫(xiě)法。

解法三：循環(huán)-動(dòng)態(tài)規(guī)劃-更進(jìn)一步內(nèi)存優(yōu)化

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];
    }
}

解法三分析

根據(jù)m和n的大小來(lái)決定是橫向還是縱向掃描，可更加節(jié)約內(nèi)存。

總結(jié)

套路就是這么明顯，只是二維情況下多了一個(gè)根據(jù)行列大小來(lái)優(yōu)化內(nèi)存的情況。

相應(yīng)例題的 Github