商品数据包网站开发,天津站设计单位,海南建设教育执业网站,百度seo如何优化上篇文章我们简单入门了动态规划#xff08;一般都是简单的上楼梯#xff0c;分析数据等问题#xff09;点我跳转#xff0c;今天给大家带来的是路径问题#xff0c;相对于上一篇在一维中摸爬滚打#xff0c;这次就要上升到二维解决问题#xff0c;但都用的是动态规划思… 上篇文章我们简单入门了动态规划一般都是简单的上楼梯分析数据等问题点我跳转今天给大家带来的是路径问题相对于上一篇在一维中摸爬滚打这次就要上升到二维解决问题但都用的是动态规划思想嘛所以大差不差且听我慢慢道来。 还是用一样的方法用同样的分析思路和技巧来分析问题解决问题。 路径规划 不同路径 状态表示 这道题我们需要知道的是从左上角位置走到右下角位置总共有多少的路径我们可以将问题拆分题目中所说机器人每次只能向下或者向右移动一步所以我们到达右下角位置是怎么到达的呢 如图 所以到达目标的方法就是到达这两个位置方法的总和。 因此这道题的状态表示就是到达ij位置总共的方法数。 状态转移方程 有了上边的分析我们可以很清晰地知道 状态转移方程为 dp[i][j]dp[i-1][j]dp[i][j-1] 初始化 初始化顺序即填表顺序是从左上角到右下角但是我们应该怎么初始化呢如果套用我们的状态转移方程我们会发现在数租的边缘部分一定会遇到越界的情况。 所以在初始化时我们可以将数组多开一行一列这样就可以解决越界访问的问题如何初始化这个表格呢我们来试着分析。 其他位置全部初始化为0这样就可以避免多开的数组影响我们后续的得到的结果。 填表顺序 填表顺序就是从左上角向左下角进行填写。 返回值 很简单就是返回填表后到达i,j位置时的值即可 接下来我们就可以根据分析出的结论写代码了。 class Solution {
public:int uniquePaths(int m, int n) {//new出一个二维数组并将他们的值初始化为0vectorvectorint dp(m1,vectorint(n1));//这里应该怎么给空间啊dp[0][1]1;for(int i1;im;i)//先填每一行for(int j1;jn;j)//再填每一列 dp[i][j]dp[i-1][j]dp[i][j-1];return dp[m][n];}
};这里还有一道十分相仿的题目多了一步扩展的思维而已尝试一下吧 不同路径2 第二道题 珠宝的最高价值 如果说上一道题对标的是上一篇中的上楼梯的方法数那么这道题对标的就是上楼梯最小花费。 思路和上一道题目很像一起来看一看。 状态表示 同样要创建一个二维数组到达ij位置可以拿到的珠宝价值最高那么状态表示就是到达ij位置能拿到的最大珠宝价值说白了就是所以路径中求和最大的一条路径。 状态转移方程 移动方式和上一道题目一样但是相比于上一道题目的相加这道题目就是从上边或者左边到达ij位置时他们两个谁的路径和最大。因为上一道题目已经解释很清楚了这里就不再画图赘述。 dp[i][j]max(dp[i-1][j],dp[i][j-1]; 填表顺序 从左上角向右下角。要注意是从下表为1,1位置开始填表的。 初始化 初始化方式和前边那道题目大同小异只不过我们多开的数组默认为0不用管就行因为第一个位置只需要加上他这个位置的财宝价值即可。 返回值 返回到达左下角位置能达到的最高价值数。 我们还是直接来展示代码吧毕竟和前边那道题很像除了状态转移方程不同。 代码如下
class Solution {
public:int jewelleryValue(vectorvectorint frame) {int mframe.size();int nframe[0].size();vectorvectorint dp(m1,vectorint(n1));for(int i1;im;i)for(int j1;jn;j)dp[i][j]max(dp[i][j-1],dp[i-1][j])frame[i-1][j-1];return dp[m][n];}
};第三道题 下降路径最小和 首先来进行题目解析这道题目只需要从上到下找到最小的路径即可而且在某位置可以向下边三个位置进行跳转。 状态表示 状态表示就是到达ij位置时需要的最小路径和然后找出最后一行中最小的就找到了最小路径下降和。 状态转移方程 可以来画图分析一下 根据我们的状态表示我们需要找到最小路径和只需要找到这个位置上边三种情况的最小路径和即可。 当然到达ij位置时还需要加上ij位置上的值。 故而状态转移方程为 dp[i][j]min(dp[i-1][j-1],min(dp[i-1][j1],dp[i-1][j]))matrix[i-1][j-1];//要注意这里位置的对应 这里状态对应的问题后边会解释到。 初始化 这里初始化是一个问题问题在于在我们求第一行时第一行的上边并没有数据访问dp[-1][-1]势必会造成越界访问如何解决呢有了上边题目的铺垫只需要扩展数组即可。 相信大家已经看到了上边的画图中分别用两种颜色标记如何初始化才能不影响后续的结果呢 因为这道题目的数组开的并不规则所以对应位置容易混淆如果你匆匆写代码的话势必会出现这样的问题 还会出现这样的问题 第一种就是没有空控制好dp表的填写导致初始化时的INT_MAX参与了运算第二种就是因为多开两列多开一行导致的位置判断不准确以至于越界访问了。 填表顺序 很明显从上往下进行填表 返回值 这里返回值和之前不太一样需要找到最后一行元素中最小的一个然后返回即可。 代码如下一定要尝试自己写一下这道题是正方形表格但是我作为长方形表格来做了大家可以忽略这些小细节哈。
class Solution {
public:int minFallingPathSum(vectorvectorint matrix) {int mmatrix.size();int nmatrix[0].size();vectorvectorint dp(m1,vectorint (n2,INT_MAX));//怎么把两边初始化为int_max;//coutint_max;for(int k0;kn1;k){dp[0][k]0;}for(int i1;im;i){for(int j1;jn1;j)//这里要注意只需要初始化我们需要的部分{dp[i][j]min(dp[i-1][j-1],min(dp[i-1][j1],dp[i-1][j]))matrix[i-1][j-1];//要注意这里位置的对应}}//此时只需找到最后一行的最小值。int retINT_MAX;for(int j1;jn;j){retmin(ret,dp[m][j]);}return ret;}
};本文到此结束感谢大家观看有问题及时提出我会积极解决的。
