62. Unique Paths - Medium

前往題目

之前寫的文章

思路

這次自己寫出來了，只是用的是top-down而非bottom-up

1. 第一行和第一列一定都是1，因為只能向右和向下走
2. 每一格都是上與左一格的和
3. 最後終點即是答案

Code

top-down

class Solution {
    public int uniquePaths(int m, int n) {
        
        int[][] grid = new int[m][n];

        // Start point
        grid[0][0] = 0;
        
        // Fill in initial value 1
        for (int col = 0; col < n; ++col) {
            grid[0][col] = 1;
        }
        for (int row = 0; row < m; ++row) {
            grid[row][0] = 1;
        }

        for (int row = 1; row < m; ++row) {
            for (int col = 1; col < n; ++col) {
                // 上加左一格
                grid[row][col] = grid[row - 1][col] + grid[row][col - 1];
            }
        }

        // 終點
        return grid[m - 1][n - 1];
    }
}

bottom-up

class Solution {
    public int uniquePaths(int m, int n) {
        // result row
        int[] row = new int[n];
        // bottom row is with only 1 possibility of each item
        Arrays.fill(row, 1);

        // Iterate through all rows, except bottom
        for (int i = 0; i < m - 1; ++i) {
            int[] newRow = new int[n];
            Arrays.fill(newRow, 1);
            
            // Iterate through the items from right to left
            // Except the right most item
            for (int j = n - 2; j >= 0; --j) {
                // Right plus down
                newRow[j] = newRow[j + 1] + row[j];
            }
            // For next round cal.
            row = newRow;
        }
        return row[0];
    }
}