【数组】Unique Paths

题目：

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

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 (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

思路：

这道题看上去有点摸不到头脑，其实细想，到达某一点路径数就等于到达它上一点和左边点的路径数之和。这样，我们就可以建立一个二维数组，进行求解即可。

/**

 * @param {number} m

 * @param {number} n

 * @return {number}

 */

var uniquePaths = function(m, n) {

    var f=[];

    for(var i=0;i<m;i++){

        f[i]=[];

    }

    for(var i=0;i<n;i++){

        f[0][i]=1;

    }

    for(var i=0;i<m;i++){

        f[i][0]=1;

    }

    for(var i=1;i<m;i++){

        for(var j=1;j<n;j++){

            f[i][j]=f[i-1][j]+f[i][j-1];

        }

    }

    return f[m-1][n-1];

};

巴特西

【数组】Unique Paths

最新文章

热门文章