迁安建设局网站,网络营销推广的标准,wordpress 常用标签,品牌设计广告公司目录 一、什么是动态规划#xff1f;
二、动态规划的使用步骤
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
三、试题讲解
1.最小花费爬楼梯
2.下降路径最小和
3.解码方法 一、什么是动态规划#xff1f; 动态规划#xff08;Dynamic Programming
二、动态规划的使用步骤
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
三、试题讲解
1.最小花费爬楼梯
2.下降路径最小和
3.解码方法 一、什么是动态规划 动态规划Dynamic Programming简称dp是一种通过将复杂问题分解为更小的子问题来解决的算法思想尤其适用于具有重叠子问题和最优子结构的优化问题。其核心目标是避免重复计算通过存储中间结果记忆化来提升效率。
动态规划 vs 分治法 共同点都将问题分解为子问题。 区别 分治法如归并排序的子问题独立无重叠无需存储中间结果。 动态规划的子问题有重叠需存储中间结果避免重复计算。
二、动态规划的使用步骤 为了方便理解下面我将从感性的角度来给大家讲解动态规划的使用步骤
1.状态表示 首先在解决问题的时候我们通常会使用一块空间来记录已处理的数据我们把这块空间叫作dp表。 当我们在解决一个小问题时需要借助之前已解决的问题的数据就可以到dp表里面查当前这个小问题解决后继续把它相关的信息存到dp表然后继续解决下一个小问题。 这个dp表中的一小块数据表示什么这些问题指的就是状态表示。在用动态规划解决问题时要面对最重要的问题就是dp表的状态应该表示是什么
在解决这个问题时我们通常都是从这几个角度去思考
1.经验题目要求2.分析问题的过程中发现重复子问题。3.当我们发现子问题后假设前或后几个小问题已经解决思考我们在解决当前问题时有没有需要前面已解决的问题的什么信息
2.状态转移方程 dp[i]等于什么这就是状态转移方程。它通常要依赖于已经计算过的状态。
3.初始化
在创建好dp表后主要任务就是对dp表的填写初始化dp表的作用有以下两点
保证填表的时候不越界。保证填表的正确性。
4.填表顺序 为使填写当前状态的时候所需要的状态已经计算过了。
5.返回值 最后结合题目要求和状态表示计算结果并返回。
三、试题讲解
1.最小花费爬楼梯 首先我们分析题目我们的起点是0或1的位置而终点是n位置注意不是n-1位置。我们在爬楼梯时支付一次费用可以爬一个或两个台阶。 当我们尝试从动态规划方向去解决那么我们试着去构造一下相同的子问题并且假设它已经解决。
注为了方便在下文我都会把动态规划简称为“动规” 用动规解题过程中在找子问题时我总结了一个很厉害的小技巧就是保留主问题的逻辑而换一个问题的对象。比如这里主问题是从起点爬到楼顶的最小花费那么构造子问题时我们只需要保留这个问题的逻辑而把楼顶这个对象改成任意位置i。那么我们就得到了一个子问题即从起点爬到i位置的最小花费。然后我们再假设前面的相同的子问题已经解决。
比如 动规题复杂多变以上技巧可以解决大部分的基础动规题但更多的只是作为一个小经验并不是所有动规题都可以通过构建子问题来解决的。 在解一个题时状态表示可以是很多不同的状态表示就决定了不同的状态转移方程而要判断一个状态表示是否正确只需看是否能根据该状态表示推出正确的状态转移方程。
能够理解上图那么动态规划的五步骤就水到渠成了。 状态表示 dp[i]表示爬到i时的最小花费状态转移方程 dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2])初始化 dp表初始化为全0填表顺序 从下标为2的位置开始并且从左往右填写返回值 return dp[n] 代码示例
class Solution {
public:int minCostClimbingStairs(vectorint cost){int ncost.size();vectorint dp(n1);//默认值就是0不用初始化for(int i2;in;i) dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);return dp[n]; }
}; 除了刚才的状态表示我们还可以换一个只需要改变一下子问题同样的技巧主问题逻辑不变把起点这个对象改成任意位置i 那么我们就得到了一个子问题即从i位置爬到楼顶的最小花费。 状态表示 dp[i]表示从i爬到楼顶的最小花费状态转移方程 dp[i]cost[i]min(dp[i1],dp[i2])初始化 dp[n-1]cost[n-1]dp[n-2]cost[n-2]填表顺序 从右往左返回值 return min(dp[0], dp[1]) 我们可以发现状态表示的改变使得其他四个步骤的实现逻辑改变所以可见状态表示的重要性。
代码示例
class Solution {
public:int minCostClimbingStairs(vectorint cost){int ncost.size();vectorint dp(n);dp[n-1]cost[n-1],dp[n-2]cost[n-2];for(int in-3;i0;i--) dp[i]cost[i]min(dp[i1],dp[i2]);return min(dp[0],dp[1]); }
}; 提示空间优化在我们填写某一个状态的时候只需要使用它的前两个状态所以可以把dp数组简化为两个变量就可以解决问题需要注意变量的更新。通常把该优化方法叫做“滚动数组”。很多基础动规都可以进行这样的优化大家可以试着去实现这一点在后面也不再提。 提示为了减少逻辑上的赘述在以下题解中我都只会讲解一种状态表示作为示例。
2.下降路径最小和 通过上一题找子问题的经验我们可以这样做
抓住主问题从第一行任意位置下降到最后一行的任意一个位置的最小和。 保留问题的主逻辑把对象“第一行任意位置”或“最后一行任意位置”更改比如更改“最后一行任意位置”为“第i行的任意位置j”。得到子问题即从“第一行任意位置下降到第i行的任意位置j的最小和”。 接下来假设与它相同的子问题都解决并利用它们的结果。如下 动规五步骤 状态表示 dp[i][j]从第一行任意位置下降到第i行j列的最小和状态转移方程 dp[i][j]matrix[i][j]min(dp[i-1][j-1]min(dp[i-1][j]dp[i-1][j1]) )初始化越界区域如下 创建(n1)*(n2)的dp表初始化为全INT_MAX这样创建dp表减少了为防止越界而做特殊判断带来的成本,再将第一行初始化为全0。把dp表初始化为全INT_MAX是为了防止越界区域参与最小值的筛选。再把第一行初始化为全0是逻辑需要总的目的都是为了保证填表的正确性。 填表顺序 从上到下从左往右或从右往左只要能保证在填写当前状态时需要的状态已计算过即可返回值 返回最后一行的最小值 代码示例
class Solution {
public:int minFallingPathSum(vectorvectorint matrix){int nmatrix.size();//题目明确指出是方形所以行数和列数都一样。vectorvectorint dp(n1,vectorint(n2,INT_MAX));for(int j0;jn2;j) dp[0][j]0;for(int i1;in;i)for(int j1;jn;j)dp[i][j]matrix[i-1][j-1]min(min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j1]);int retINT_MAX;for(int j1;jn;j) retmin(ret,dp[n][j]);return ret;}
};
3.解码方法 主问题 一个非空字符s的解码方法的总数。但我们好像无法从中获取到可以更改的对象再回去观察上面我们解决的两道问题。它们主问题的逻辑中都是带有区间式的比如第一题从起点到终点第二题从第一行到最后一行。那么如果我们还想要那个找子问题的技巧去确定状态表示那么在总结主问题时就要朝着带有区间式的方向去想。 这里我们可以把主问题总结为从s字符串的下标0开始到下标n-1结束的解码方法总数。那么这样我们就构造出了一个区间“开始”——“结束”。子问题就好构建得多了。
子问题从下标0开始到下标i结束的解码方法总数。 状态表示 dp[i]表示从下标0开始到下标i结束的解码方法总数状态转移方程 解决了状态表示但这个题的难点主要在于状态转移方程。 我们可以把单独解码与和前一个联合解码分开讨论。如果单独解码成功相当于在i-1的所有解码方法中统一加上一个s[i]所以为dp[i-1]解码失败的话说明不能单独解码所以结果为0。 同理联合解码成功相当于在i-2的所有解码方法中统一加上一个s[i]与s[i-1]的复合所以为dp[i-2]解码失败的话说明不能联合解码所以结果为0。最后只需要把单独解码与联合解码的结果相加。 初始化 因为我们在用dp[i]时需要用到dp[i-1]和dp[i-2]的状态所以最好把dp[0]和dp[1]初始化。dp[0]可以这样写dp[0]s[i]!0但dp[1]的初始化会比较麻烦它的初始化逻辑和上面的状态转移方程是一样的。而在下面填表时同样要用到这样的逻辑就会显得很累赘。 我们可以使用这样一个初始化技巧 那么可以做一个n1大小的dp表然后错开一位表示即 dp[i]表示从下标0开始到下标i-1结束的解码方法总数。为保证后面的填表顺序正确我们需要dp[1]s[i]!0这是必然的。而dp[0]该初始化为什么我们可以思考什么时候用到dp[0]即s[0]与s[1]解码成功时那么它必然是dp[0]1 填表顺序从dp的2下标开始并从左往右。返回值 return dp[n] 代码示例
class Solution {
public:int numDecodings(string s){vectorint dp(s.size()1,0);dp[1]s[0]!0,dp[0]1;for(int i2;idp.size();i){int m(s[i-2]-0)*10s[i-1]-0;if(s[i-1]!0) dp[i]dp[i-1];if(m10m26) dp[i]dp[i-2];}return dp.back();}
}; 非常感谢您能耐心读完这篇文章。倘若您从中有所收获还望多多支持呀
