美文网首页
Unique Paths - dynamic programmi

Unique Paths - dynamic programmi

作者: Star_C | 来源:发表于2018-03-29 13:03 被阅读0次

Question

from lintcode
A robot is located at the top-left corner of a m x n grid.

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.

Notice
m and n will be at most 100.

Have you met this question in a real interview? Yes
Example
Given m = 3 and n = 3, return 6.
Given m = 4 and n = 5, return 35.

Idea

One path to start.
f[0][0] = 1

Number of paths to reach each 1st row (0-index) element = paths from left, cuz there're no top elements
f[0][any column] = f[0][previous column]

Number of paths to reach each 1st column (0-index) element = paths from top, cuz there're no left columns
f[any row][0] = f[previous row][0]

Number of paths to reach position x,y = paths from left + paths from top
f[row][column] = f[row][column - 1] + f[row - 1][column]

/**
 *
 * One path to start.
 *  f[0][0] = 1
 *
 * Number of paths to reach each 1st row (0-index) element = paths from left, cuz there're no top elements
 *  f[0][any column] =  f[0][previous column]
 *
 * Number of paths to reach each 1st column (0-index) element = paths from top, cuz there're no left columns
 *  f[any row][0] = f[previous row][0]
 *
 * Number of paths to reach position x,y = paths from left + paths from top
 * f[row][column] = f[row][column - 1] + f[row - 1][column]
 *
 * You need to remember two rows of result.
 */
public class Solution {
    /**
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    public int uniquePaths(int m, int n) {
        int rowLen = m, colLen = n;
        int[][] ways = new int[this.rowsToRemember][colLen];

        // f[0][0] = 1
        ways[0][0] = 1;
        
        // f[0][any column] = f[0][prev Column], for 1st row has no upper rows
        for(int column = 1; column < colLen; column++)
            ways[rowIndexOf(0)][column] = ways[rowIndexOf(0)][column - 1];

        // f[any row][0] = f[prev row][0], for 1st column has no left column
        for(int row = 1; row < rowLen; row++)
            ways[rowIndexOf(row)][0] = ways[rowIndexOf(row - 1)][0];

        // f[row][column] = f[row][column - 1] + f[row - 1][column]
        for(int row = 1; row < rowLen; row++)
            for(int column = 1; column < colLen; column++) {
                ways[rowIndexOf(row)][column] = ways[rowIndexOf(row)][column - 1] + ways[rowIndexOf(row - 1)][column];
            }

        return ways[rowIndexOf(rowLen - 1)][colLen - 1];
    }

    private int rowsToRemember = 2;

    private int rowIndexOf(int i) {
        return i % rowsToRemember;
    }
}

相关文章

网友评论

      本文标题:Unique Paths - dynamic programmi

      本文链接:https://www.haomeiwen.com/subject/zxsmcftx.html