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.
Solution 1:
public int uniquePaths(int m, int n) { int[][] f = new int[m][n]; for(int i=0; i<m; i++) { f[i][0] = 1; } for(int i=0; i<n; i++) { f[0][i] = 1; } for(int i=1; i<m; i++) { for(int j=1; j<n; j++) { f[i][j] = f[i-1][j]+f[i][j-1]; } } return f[m-1][n-1]; }
Solution 2:
public int uniquePaths(int m, int n) { int[] f = new int[n]; f[0] = 1; for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { f[j] = f[j] + (j>0?f[j-1]:0); } } return f[n-1]; }
补充下C++的代码:
int uniquePaths1(int m, int n) { vector<vector<int>> f(m, vector<int>(n,1)); for(int i=1; i<m; i++) { for(int j=1; j<n; j++) { f[i][j] = f[i-1][j] + f[i][j-1]; } } return f[m-1][n-1]; } int uniquePaths2(int m, int n) { vector<int> f(n, 1); for(int i=1; i<m; i++) { for(int j=1; j<n; j++) { f[j] += f[j-1]; } } return f[n-1]; }
相关推荐
1、记忆化 2、二维dp 3、滚动优化
62.unique-paths.cpp [TODO] 5. 最长回文子串.cpp 第 3 天: [TODO] 96.unique-binary-search-trees.cpp [TODO] 70. 爬楼梯.cpp [TODO] 746. min-cost-climbing-stairs.cpp 第 4 天: [待办事项] leetcode/1143。 ...
扩展矩阵leetcode ...uniquePaths 63.不同路径II uniquePathsWithObstacles 139.单词拆分 wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75.颜色分类 sortColors 179.最大数 largestNumber 324.摆
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 Java Associated Documents and Resources Peter norvig神牛Python代码写的很飘逸,果然是有LISP...
leetcode 答案 leetcode 08/18 Unique Paths 应该是简单的数学排列组合问题,提炼一下其实就一句话:有m个黑球,n个白球,有多少种不同的排列方式。 我数学太差,没找到答案,直接上了动态规划。 Unique Paths II ...
unique_paths.py(类似于 chess_board.c!)+ unique_paths2.py chess_board.c 效率测试 bin_search.py 素数.py 零知识.py Leetcode:现在很多小方案都是leetcode,我主要是为了好玩。 著名算法:Knuth-Morris-Pratt...
leetcode 530 力码 全部的: 易(173/237+x) 中(144/437+x) 硬(4/x) 问题 1.Two Sum(dict) 7.(跳过)(数学) 9.(跳过)(串串技巧) ...47/46....54/59....62.独特的路径 63/62.Unique Paths 2 64.最小路径和
##NO.62 Unique Paths 这道题是一道动态规划的题,还算简单。状态转移方程为: path[i][j] = path[i-1][j] + path[i][j-1]; i和j表示的是i*j的网格从左上角到右下角的路径数量。 并且初始的时候path[i][j]都为1。 为...
62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/03/09 70.Climbing Stairs, 198.House Robber, 55.Jump Game 72.Edit Distance, 97.Interleaving String, 115.Distinct Subsequences 2017/04/24 ...
leetcode正方体收藏TakeUforward-...Unique Paths Reverse Pairs (Leetcode) 从 GFG 中通过拼图(自行搜索) Day4: (Hashing) 2 Sum 问题 4 Sum 问题 Longest Consecutive Sequence Longest Subarray with 0 sum 给定
uniquePaths = function(m, n) { let dp = new Array(m).fill(0).map(() => new Array(n)); // dp[r][c] represents the number of possible paths from row = 0, col = 0 to row = r, col = c for (let row = 0; ...
62.独特的路径 63.Unique Paths II 64.最小路径和 70.爬楼梯 72.编辑距离 122. 买卖股票的最佳时机 II 152.最大积子阵列 198.强盗 322.硬币变化 贪心算法 45.跳跃游戏II 55.跳跃游戏 哈希 1.二和 3.最长不重复字符的...
Unique Paths II N-Queens N-Queens II Restore IP Addresses Combination Sum Combination Sum II Combination Sum III Generate Parentheses Sudoku Solver Word Search 总结 分治法 Pow(x,n) Sqrt(x) 贪心法 Jump...