Unique Paths
来自 <https://leetcode.com/problems/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.
题目解读:
一个机器人在二维m x n网格的最左上方(在下面的例子中标识为‘Start’)。这个机器人只能向右或者向下移动,它想到达二维网格的最右下方(在下面的例子中标识为‘Finish’)。
一共有多少种不同的路径?
Note:
m和n最大为100.
解析:
这是一个动态规划的题,如果把任意网格作为最终目的地。则到达其位置的不同路径种数为到其上方和左方不同路径种数之和。
Java代码:
public class Solution { //动态规划 public int uniquePaths(int m, int n) { if(0==m || 0==n) return 0; //一行一列只能有一种情况 if(1==m && 1==n) return 1; int[][] dynamicPlanning = new int[m][n]; //给最左端一行进行赋值1,标识从开始点到左端的任意一个地方只有一种办法 for(int i=0; i<m; i++) dynamicPlanning[i][0] = 1; //给最上放一行赋值1,表示从开始点到上端任意一个地方只有一种方法 for(int i=0; i<n; i++) dynamicPlanning[0][i] = 1; for(int i=1; i<m; i++) { for(int j=1; j<n; j++) //到达二维数组中任意一点的总和为其位置上方和左方元素之和 dynamicPlanning[i][j] = dynamicPlanning[i-1][j] + dynamicPlanning[i][j-1]; } return dynamicPlanning[m-1][n-1]; } }
算法行能:
相关推荐
1、记忆化 2、二维dp 3、滚动优化
动态规划 5.最长回文子串 longestPalindrome(中心扩展法实现) 62.不同路径 uniquePaths 63.不同路径II uniquePathsWithObstacles 139.单词拆分 wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75....
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。 ...
我数学太差,没找到答案,直接上了动态规划。 Unique Paths II mod之后,可能数学公式就不能简单地给出答案了。但对我来说,其实和前一题没区别。动态规划处理这种问题,早就是牛刀杀鸡了。。 Single Number 碰巧我...
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 Java Associated Documents and Resources Peter norvig神牛Python代码写的很飘逸,果然是有LISP...
动态规划(非常基础)/递归 最长子序列.py 制作_change.py 子集.py super_digit.py unique_paths.py(类似于 chess_board.c!)+ unique_paths2.py chess_board.c 效率测试 bin_search.py 素数.py 零知识.py ...
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.最小路径和
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 ...
这道题是一道动态规划的题,还算简单。状态转移方程为: path[i][j] = path[i-1][j] + path[i][j-1]; i和j表示的是i*j的网格从左上角到右下角的路径数量。 并且初始的时候path[i][j]都为1。 为方便起见,这里我从...
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; ...
动态规划 10.正则表达式匹配 32.最长有效括号 53.最大子阵列 62.独特的路径 63.Unique Paths II 64.最小路径和 70.爬楼梯 72.编辑距离 122. 买卖股票的最佳时机 II 152.最大积子阵列 198.强盗 322.硬币变化 贪心算法...
leetcode正方体收藏TakeUforward-SDE_180 要了解整个列表和其他内容,如项目、简历、如何进行面试……观看整个视频: 在以下位置找到展示位置系列: 第一天:(数组) 在 N+1 整数数组中查找重复项。 (描述中的问题...
动态规划 Triangle Maximum Subarray Maximum Product Subarray Longest Increasing Subsequence Palindrome Partitioning II Maximal Rectangle Best Time to Buy and Sell Stock III Best Time to Buy and Sell ...