- 浏览: 171726 次
- 性别:
- 来自: 济南
文章分类
最新评论
这篇文章介绍unique path等一系列的题目,它们属于二维动态规划的问题,之前一篇文章讲过最长公共子序列(LCS), 最长递增子序列(LIS), 最长非降子序列。有兴趣的可以看一下,这些都是经典的二维动规问题。
1,Unique Paths
给定一个m*n的矩阵,一个机器人在这个矩阵的左上方,它试图走到这个矩阵的右下方,规定机器人只能往右和往下两个方向走,问有多少种不同的路径。
我们把这个矩阵抽象成一个二维数组grid,机器人开始的位置就是grid[0][0],它可以往下走,也可以往右走,我们初始化数组让它的第0列和第0行的值都1,因为机器人到这些地方只有一条路。对于其它的地方grid[i][j] = grid[i-1][j] + grid[i][j-1],因为到达(i, j)点必须经过(i, j-1)和(i, j-1),这样递推式就写出来了。代码如下:
2,Unique Paths II
给定一个二维数组,里面的值都是0或1,0代表可以到达,1代表不可以到达。其他规则和上题一样,问有多少种不同的方法。
唯一不同的就是多了障碍物,如果要走到终点,必须要绕过障碍物,换句话说有障碍物的点的值都为0。还要值得注意的是在第0列和第0行中,如果有障碍物,那么障碍物后面的路都是不通的,都要设置为0。代码如下:
3,Minimum Path Sum
给定一个m*n的矩阵,里面包含着非负整数,从左上方到右下方,找出最小带权路径。
这是第一题的变形,在初始化第0列的时候 grid[i][0] += grid[i-1][0]; 第0行的初始化为grid[0][i] += grid[0][i-1]; 第(i,j)点的值我们仅需要去一个最小的就可以了,grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1]) + grid[i][j] (i>=1, j>=1)。代码如下:
1,Unique Paths
给定一个m*n的矩阵,一个机器人在这个矩阵的左上方,它试图走到这个矩阵的右下方,规定机器人只能往右和往下两个方向走,问有多少种不同的路径。
我们把这个矩阵抽象成一个二维数组grid,机器人开始的位置就是grid[0][0],它可以往下走,也可以往右走,我们初始化数组让它的第0列和第0行的值都1,因为机器人到这些地方只有一条路。对于其它的地方grid[i][j] = grid[i-1][j] + grid[i][j-1],因为到达(i, j)点必须经过(i, j-1)和(i, j-1),这样递推式就写出来了。代码如下:
public class Solution { public int uniquePaths(int m, int n) { int[][] result = new int[m][n]; for(int i = 0; i < m; i++) { result[i][0] = 1; } for(int j = 0; j < n; j ++) { result[0][j] = 1; } for(int i = 1; i < m; i++) for(int j = 1; j < n; j++) { result[i][j] = result[i-1][j] + result[i][j-1]; } return result[m-1][n-1]; } }
2,Unique Paths II
给定一个二维数组,里面的值都是0或1,0代表可以到达,1代表不可以到达。其他规则和上题一样,问有多少种不同的方法。
唯一不同的就是多了障碍物,如果要走到终点,必须要绕过障碍物,换句话说有障碍物的点的值都为0。还要值得注意的是在第0列和第0行中,如果有障碍物,那么障碍物后面的路都是不通的,都要设置为0。代码如下:
public class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) { if(obstacleGrid[i][j] == 1) obstacleGrid[i][j] = 0; else if(i == 0 && j == 0) obstacleGrid[i][j] = 1; else if(i == 0) obstacleGrid[0][j] = obstacleGrid[0][j-1]; else if(j == 0) obstacleGrid[i][0] = obstacleGrid[i-1][0]; else obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]; } return obstacleGrid[m-1][n-1]; } }
3,Minimum Path Sum
给定一个m*n的矩阵,里面包含着非负整数,从左上方到右下方,找出最小带权路径。
这是第一题的变形,在初始化第0列的时候 grid[i][0] += grid[i-1][0]; 第0行的初始化为grid[0][i] += grid[0][i-1]; 第(i,j)点的值我们仅需要去一个最小的就可以了,grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1]) + grid[i][j] (i>=1, j>=1)。代码如下:
public class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; for(int i = 1; i < m; i++) { grid[i][0] += grid[i-1][0]; } for(int i = 1; i < n; i++) { grid[0][i] += grid[0][i-1]; } for(int i = 1; i < m; i++) for(int j = 1; j < n; j++) { grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1]) + grid[i][j]; } return grid[m-1][n-1]; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 221Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 219You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 336Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 325Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 443Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 498Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 423Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 611Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 420The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 378Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 511Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 521Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 364All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 853Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 876Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 547Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 592Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 757Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 724You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 623For a undirected graph with tre ...
相关推荐
动态规划总结与题目分类 一、简单基础dp 1、递推: 2、背包 3、LIS 4、LCS 二、区间dp 四、数位dp 五、概率(期望) dp 六、状态压缩dp 七、数据结构优化的dp 1、二进制优化 2、单调队列优化 3、斜率优化 4、四边形...
一共有32讲,并且有动态规划状态转移方程的总结。 第一节 动态规划基本概念 第二节 动态规划分类讨论 动态规划入门3 动态规划入门4 动态规划入门5 动态规划入门6 动态规划入门7 动态规划入门8……
基本动态规划算法总结 最长子序列探索 (最长非降子序列 + 最长公共子序列 最优路径搜索 ( 点数值三角形的最优路径搜索 +边数值矩形的最优路径搜索) 装载问题 0−1背包问题 二维0−1背包问题 插入乘号问题
4、总结一下你知道的可以用动态规划求解的问题,简要说明每个问题递归的子问题空间。 问题1、火柴棍游戏:2堆火柴棍,2人轮流拿。拿的规则如下:1、每次至少拿一根;2、只能从一堆里拿;3、第一堆火柴棍最多拿3根;4...
leetcode动态规划总结Leetcode 总结 C++ 用 C++ 编写的 LeetCode 问题摘要。 请查看更多信息。 对于 Python 版本,请检查 . 对于 Java 版本,请检查 . 带*号的题号,表示本题与原题不同。 基本数据结构 - 广度优先...
运筹学课程总结之后绘制的思维导图
实验二 用动态规划法求解0/1背包问题 实验三 用贪心算法求解Prim算法 实验四 用回溯法求解N后问题 实验五 用分支限界法实现旅行售货员问题 这些实验的大部分源代码都是书上的, 我用的是WindowsXP SP2 VisualC++6.0...
昨天在牛客网上做笔试题,碰到了一道题动态规划做了一晚上都没做出来,最后看着别人的答案才勉强做出来,太菜了,今天总结一下。 动态规划思路: 1、找到状态和选择,确定当前状态和转换 2、明确dp数组/或函数的定义...
本资源主要是汇集了自己刷题时总结下来的一些经典题目:包括二分、字符串替换、DP问题、动态规划、最长子序列、DFS、BFS、回溯算法等,旨在记录和查看复习,为了不断提升,不断更新补充。也包括链表的一些基础,有...
在第五章中更是对动态规划常见的一些体型进行了总结整理,包括“最长公共子序列,最长公共子串,背包,最大子数组和”;最后summary总结整理了链表常见的问题包括“链表是否有环,链表环的入口,是否相交,排序等”...
第20节 暴力递归到动态规划(二).mp4 第21节 暴力递归到动态规划(三).mp4 第22节 暴力递归到动态规划(四).mp4 第23节 暴力递归到动态规划(五).mp4 第24节 暴力递归到动态规划(六).mp4 共48节课
运筹学课程总结之后绘制的思维导图
算法设计技巧10.1 贪婪算法10.1.1 一个简单的调度问题10.1.2 Huffman编码10.1.3 近似装箱问题10.2 分治算法10.2.1 分治算法的运行时间10.2.2 最近点问题10.2.3 选择问题10.2.4 一些运算问题的理论改进10.3 动态规划...
4第四章 动态规划 5第五章 图与网络 6第六章 排队论 7第七章 对策论 8第八章 层次分析法 9第九章 插值与拟合 10第十章 数据的统计描述和分析 11第十一章 方差分析 12第十二章 回归分析 13第十三章 微分方程建模 ...
两年ACM竞赛所有算法总结,这里包含最短路、最小生成树、动态规划、字符串匹配、博弈、大数、Hash、排序、二分匹配、并查集、最大流、欧拉函数、扩展欧几里得等
详细介绍了VMProtect的特点,同时讲解了vmp的逆向分析和静态还原点。...(五)转换汇编指令——动态规划 (六)寄存器染色 基本块内的寄存器轮转 基本块间的寄存器轮转 寄存器的二义性问题 识别寄存器的二义性的步骤
经典算法,让你沉醉其中无法自拔。 一、A*搜索算法 一(续)、A*,Dijkstra,BFS 算法性能比较及 A*算法的应用 二、Dijkstra 算法初探 二(续)、彻底理解 Dijkstra 算法 二(再续)、Dijkstra 算法...三、动态规划算法
PowerPoint模板内容页,由62张蓝色动态微立体幻灯片图表制作。图表类型丰富,框架完整,非常实用。 年终工作总结PPT目录: 一、工作回顾(近年来工作情况) 二、自我评价(对自己的看法) 三、工作体会(对工作的...
在LeetCode等平台上,针对特定类型题目进行专题训练,例如,你可以专门花一段时间集中攻克动态规划的问题,然后转至图论相关题目,每个主题完成后都要梳理总结,整理成便于查阅的笔记。 二、比赛策略 题目分析的实际...
动态规划: 排序专题: 程序员代码面试指南 : chapter2 : 链表部分题目: LeetCode官方算法精选 初级算法49题: 数组系列: 字符串系列 链表系列 二叉树系列 排序系列 动态规划系列 设计系列 数学系列 其它系列 算法...