62. Unique Paths (2D-dp)

time complexity: O(n^2)

class Solution {
    public int uniquePaths(int m, int n) {
        int dp[][] = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1; // from left top corner
        for (int i = 0; i < n; i++) dp[0][i] = 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];
    }
}

from bottom...太不直覺了

class Solution {
    public int uniquePaths(int m, int n) {
        int dp[][] = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][n-1] = 1; // from button
        for (int i = 0; i < n; i++) dp[m-1][i] = 1;
        
        for (int i = m-1; i > 0; i--) {
            for (int j = n-1; j > 0; j--) {
                
                dp[i-1][j-1] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[0][0];
    }
}

a little optimization of the space, 1-D array

其實可以一行一行累加上來

因為只要計算紅匡的部分, 所以 這段 for loop 都從 1 開始

        for (int i = 1; i < m; i++) { // row, from 1 start
            for (int j = 1; j < n; j++) { // column
                dp[j] += dp[j-1];
            }
        }

因為初始了index 0, row 和 col

都為 11111, 應該說只需要初始 row index = 0的 11111

因為都用同一個一維陣列

所以當 row index = 1時

dp[j], j 1 to n 都是 111111

要算 原本的dp[1][1] ＝dp[0][1] + dp[1][0]

就只需要加上dp [j-1], 也就是 dp[j]+= dp [j-1] = == dp[1][1]

因為dp[j]本身就把dp[0][1]的值帶下來了,

只需要加上dp[1][0] (也就是dp[j-1]

dp[1][1] ＝dp[0][1] + dp[1][0]

dp[1][1] = dp[j] + dp [j-1]

class Solution {
    public int uniquePaths(int m, int n) {
        int dp[] = new int[n]; // column size
        Arrays.fill(dp, 1); //fill each row to 1 first
        for (int i = 1; i < m; i++) { // row, from 1 start
            for (int j = 1; j < n; j++) { // from index 1 column
                dp[j] += dp[j-1]; //add pre column value
            }
        }
        return dp[n-1];
    }
}