[leetcode]62. Unique Paths63. Unique Paths II -- JavaScript 代码

/** * @param {number} m * @param {number} n * @return {number} */ var uniquePaths = function(m, n) { // 建立一个 m*n的矩阵 f(x,y) = f(x-1,y) + f(x,y-1) var array = []; for(var i=0;i<m;i++){ array[i] = []; for(var j=0;j<n;j++){ if(i===0||j===0){ array[i][j] = 1; }else{ array[i][j] = 0; } } } for(i=1;i<m;i++){ for(j=1;j<n;j++){ array[i][j] = array[i-1][j]+array[i][j-1]; } } return array[m-1][n-1]; };

典型的动态规划题目，只要找到递归方程，问题就迎刃而解了：

f(x,y) = f(x-1,y) + f(x,y-1)

第63题和62题基本思路一样，就是多了个条件。DP代码如下：

/** * @param {number[][]} obstacleGrid * @return {number} */ var uniquePathsWithObstacles = function(obstacleGrid) { var row = obstacleGrid.length; if(row===0){ return 0; } var col = obstacleGrid[0].length; var array = []; for(var i=0;i<row;i++){ array[i] = []; if(obstacleGrid[i][0]==1){ break; }else{ array[i][0] = 1; } } for(j=i;j<row;j++){ array[j] = []; array[j][0] = 0; } for(i=0;i<col;i++){ if(obstacleGrid[0][i]==1){ break; }else{ array[0][i] = 1; } } for(var j=i;j<col;j++){ array[0][j] = 0; } for(i=1;i<row;i++){ for(j=1;j<col;j++){ if(obstacleGrid[i][j]==1){ array[i][j] = 0; }else{ array[i][j] = array[i-1][j] + array[i][j-1] } } } return array[row-1][col-1]; };