题目描述:
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
解析:
记忆化的二维数组
Java:
public int uniquePaths(int m, int n) { int[][] memo = new int[n][m]; for(int row = 0; row < n; row++) { memo[row][0] = 1; } for(int col = 0; col < m; col++) { memo[0][col] = 1; } for(int row = 1; row < n; row++) { for(int col = 1; col < m; col++) { memo[row][col] = memo[row-1][col] + memo[row][col-1]; } } return memo[n-1][m-1]; }
JavaScript:
var uniquePaths = function(m, n) { const memo = []; for(let i = 0; i < n; i++) { memo.push([]); } for(let row = 0; row < n; row++) { memo[row][0] = 1; } for(let col = 0; col < m; col++) { memo[0][col] = 1; } for(let row = 1; row < n; row++) { for(let col = 1; col < m; col++) { memo[row][col] = memo[row-1][col] + memo[row][col-1]; } } return memo[n-1][m-1]; };