`
随便小屋
  • 浏览: 102198 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

LeetCode-62-Unique Paths*(动态规划)

阅读更多

 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];
	}
}

 

算法行能:



 

分享到:
评论

相关推荐

    pcw0118#ZXBlog#LeetCode-62.Unique Paths(不同的路径数量)(简单dp)1

    1、记忆化 2、二维dp 3、滚动优化

    扩展矩阵leetcode-Leetcode:LeetcodeAnswer-Java

    动态规划 5.最长回文子串 longestPalindrome(中心扩展法实现) 62.不同路径 uniquePaths 63.不同路径II uniquePathsWithObstacles 139.单词拆分 wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75....

    leetcode1477-coding-for-fun:编码乐趣

    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答案-leetcode:leetcode

    我数学太差,没找到答案,直接上了动态规划。 Unique Paths II mod之后,可能数学公式就不能简单地给出答案了。但对我来说,其实和前一题没区别。动态规划处理这种问题,早就是牛刀杀鸡了。。 Single Number 碰巧我...

    leetcode分类-LeetCode:力码

    leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 Java Associated Documents and Resources Peter norvig神牛Python代码写的很飘逸,果然是有LISP...

    leetcode棋盘-Algorithms:通用算法实现

    动态规划(非常基础)/递归 最长子序列.py 制作_change.py 子集.py super_digit.py unique_paths.py(类似于 chess_board.c!)+ unique_paths2.py chess_board.c 效率测试 bin_search.py 素数.py 零知识.py ...

    leetcode530-Leetcode:新的开始

    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.最小路径和

    gasstationleetcode-leetcode:LeetcodeOJ解决方案

    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叫数-Leetcode_JS:leetcode编程题,javascript版本

    这道题是一道动态规划的题,还算简单。状态转移方程为: path[i][j] = path[i-1][j] + path[i][j-1]; i和j表示的是i*j的网格从左上角到右下角的路径数量。 并且初始的时候path[i][j]都为1。 为方便起见,这里我从...

    leetcode算法题主函数如何写-visual-your-algo:网站暂停升级中

    uniquePaths = function(m, n) { let dp = new Array(m).fill(0).map(() =&gt; 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; ...

    lrucacheleetcode-LeetcodeSolution:Leetcode刷题的分类和答案记录

    动态规划 10.正则表达式匹配 32.最长有效括号 53.最大子阵列 62.独特的路径 63.Unique Paths II 64.最小路径和 70.爬楼梯 72.编辑距离 122. 买卖股票的最佳时机 II 152.最大积子阵列 198.强盗 322.硬币变化 贪心算法...

    leetcode正方体堆叠-TakeUforward-SDE_180:TakeUforward-SDE_180

    leetcode正方体收藏TakeUforward-SDE_180 要了解整个列表和其他内容,如项目、简历、如何进行面试……观看整个视频: 在以下位置找到展示位置系列: 第一天:(数组) 在 N+1 整数数组中查找重复项。 (描述中的问题...

    cpp-算法精粹

    动态规划 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 ...

Global site tag (gtag.js) - Google Analytics