淄博三合一网站开发,甜品网站首页设计,百度做网站和推广效果怎么样,帝国cms能做手机网站吗动态规划
动态规划就像是解决问题的一种策略#xff0c;它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题#xff0c;并将每个小问题的解保存起来。这样#xff0c;当我们需要解决原始问题的时候#xff0c;我们就可以直接利…动态规划
动态规划就像是解决问题的一种策略它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题并将每个小问题的解保存起来。这样当我们需要解决原始问题的时候我们就可以直接利用已经计算好的小问题的解而不需要重复计算。 动态规划与数学归纳法思想上十分相似。
数学归纳法 基础步骤base case首先证明命题在最小的基础情况下成立。通常这是一个较简单的情况可以直接验证命题是否成立。 归纳步骤inductive step假设命题在某个情况下成立然后证明在下一个情况下也成立。这个证明可以通过推理推断出结论或使用一些已知的规律来得到。
通过反复迭代归纳步骤我们可以推导出命题在所有情况下成立的结论。 动态规划 状态表示 状态转移方程 初始化 填表顺序 返回值
数学归纳法的基础步骤相当于动态规划中初始化步骤。
数学归纳法的归纳步骤相当于动态规划中推导状态转移方程。
动态规划的思想和数学归纳法思想类似。 在动态规划中首先得到状态在最小的基础情况下的值然后通过状态转移方程得到下一个状态的值反复迭代最终得到我们期望的状态下的值。 接下来我们通过三道例题深入理解动态规划思想以及实现动态规划的具体步骤。
97. 交错字符串 - 力扣LeetCode 题目解析 状态表示
对于两个字符串之间的dp问题我们的一般的思考方式如下 选取第一个字符串的[0,i]区间以及第二个字符串的[0,j]区间当成研究对象结合题目要求来定义状态表示。 然后根据两个区间上最后一个位置的状况进行分类讨论从而确定状态转移方程。
由于这段题目里面空串是研究意义的因此我们先预处理一下原字符串前面统一加上一个占位符s1s1“ ”s2s2” “s3s3” “
根据上述思路我们很容易可以定义这样一个状态表示
定义dp[i][j]表示字符串s1中[1,i]区间内的字符串以及s2中[1,j]区间内的字符串能否拼接成s3中[1,ij]区间内的字符串。
状态转移方程 如果s3[ij]s1[i] 此时s3[ij]与s1[i]匹配如果s1[1,i-1]和s2[1,j]可以拼成s3[1,ij-1]说明s1[1,i]和s2[1,j]可以拼成s3[1,ij]此时dp[i][j]dp[i-1][j] 如果s3[ij]s2[j], 此时s3[ij]与s2[i]匹配如果s1[1,i]和s2[1,j-1]可以拼成s3[1,ij-1]说明s1[1,i]和s2[1,j]可以拼成s3[1,ij]此时dp[i][j]dp[i][j-1] 如果s3[ij]s1[i]s3[ij]!s2[j] 此时dp[i][j]false 综上所述将false设置为初始值得到状态转移方程为 dp[i][j] (s1[i] s3[i j] dp[i - 1][j]) ||(s2[j] s3[i j] dp[i][j - 1]);
初始化 根据状态转移方程我们知道想要推到ij位置的状态我们需要用到i-1jij-1位置的状态。
所以我们需要初始化第一行和第一列。 初始化第一行 第一行表示s1是空串此时s2[1,j]必须和s3[1,ij]对应相等dp[i][j]才为true。 初始化第一列 第一列表示s2是空串此时s1[1,j]必须和s3[1,ij]对应相等dp[i]j]才为true。 故初始化为 for (int j 1; j n; j) if (s2[j] s3[j])dp[0][j] true;elsebreak;for (int i 1; i m; i)if (s1[i] s3[i])dp[i][0] true;elsebreak;
填表顺序
根据状态转移方程我们知道想要推到ij位置的状态我们需要用到i-1jij-1位置的状态。 固定i改变j i的变化需要从小到大由于需要用到ij-1位置的状态所以j的变化也需要从小到大。 固定j改变i j的变化需要从小到大由于需要用到i-1j位置的状态所以i的变化也需要从小到大。
返回值
定义dp[i][j]表示字符串s1中[1,i]区间内的字符串以及s2中[1,j]区间内的字符串能否拼接成s3中[1,ij]区间内的字符串。
结合题目意思我们需要判断字符串s1中[1,m]区间内的字符串以及s2中[1,n]区间内的字符串能否拼接成s3中[1,mn]区间内的字符串。
故返回dp[m][n]
代码实现 class Solution {
public:bool isInterleave(string s1, string s2, string s3) {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int m s1.size(), n s2.size();if (m n ! s3.size())return false;s1 s1, s2 s2, s3 s3;vectorvectorbool dp(m 1, vectorbool(n 1));dp[0][0] true;for (int j 1; j n; j) if (s2[j] s3[j])dp[0][j] true;elsebreak;for (int i 1; i m; i)if (s1[i] s3[i])dp[i][0] true;elsebreak;for (int i 1; i m; i)for (int j 1; j n; j)dp[i][j] (s1[i] s3[i j] dp[i - 1][j]) ||(s2[j] s3[i j] dp[i][j - 1]);return dp[m][n];}
};
712. 两个字符串的最小ASCII删除和 - 力扣LeetCode 题目解析 状态表示
对于两个字符串之间的dp问题我们的一般的思考方式如下 选取第一个字符串的[0,i]区间以及第二个字符串的[0,j]区间当成研究对象结合题目要求来定义状态表示。 然后根据两个区间上最后一个位置的状况进行分类讨论从而确定状态转移方程。
根据上述思路我们很容易可以定义这样一个状态表示
定义dp[i][j]表示s1[0,i]和s2[0,j]区间中所有公共子序列ASCII的最大和。
状态转移方程 如果公共子序列包括s1[i]和s2[j]此时s1[i]s2[j] 此时dp[i][j]dp[i-1][j-1]s1[i]或者dp[i][j]dp[i-1][j-1]s2[j] 如果公共子序列包括s1[i]但是不包括s2[j] 因为要使得公共子序列ASCII尽可能大所以此时s1[i]!s2[j], 此时dp[i][j]dp[i][j-1]; 如果公共子序列包括s2[j]但是不包括s1[i] 因为要使得公共子序列ASCII尽可能大所以此时s1[i]!s2[j], 此时dp[i][j]dp[i-1][j]; 如果公共子序列不包括s1[i]也不包括s2[j] 因为要使得公共子序列ASCII尽可能大所以此时s1[i]!s2[j], 此时dp[i][j]dp[i-1][j-1]; 将上述情况进行合并和简化得到状态转移方程 dp[i][j] max(dp[i][j - 1], dp[i - 1][j]);if (s1[i] s2[j])dp[i][j] max(dp[i][j], dp[i - 1][j - 1] s1[i]);初始化 根据状态转移方程我们知道在推导ij位置的状态时需要用到ij-1i-1ji-1j-1以及s1i-1和s2j-1的值。
所以蓝色部分会发生越界情况此时推导这些位置的状态没有前驱值所以我们需要将这些位置的状态进行初始化。 我们可以正常对这些位置进行初始化也可以添加虚拟结点代替这些位置的虚拟化。
添加虚拟节点即多添加一行和一列代替原先需要初始化的位置现在只需要初始化绿色位置的值即可。这样做的好处是绿色位置的初始化过程可能很简单而蓝色位置的初始化过程可能稍微复杂。 我们添加虚拟节点后状态表示、状态转移方程会发生改变即 定义dp[i][j]表示s1[0,i-1]和s2[0,j-1]区间中所有公共子序列ASCII的最大和。 dp[i][j] max(dp[i][j - 1], dp[i - 1][j]);if (s1[i - 1] s2[j - 1])dp[i][j] max(dp[i][j], dp[i - 1][j - 1] s1[i - 1]); 添加虚拟结点之后有两点注意事项 初始化虚拟节点必须保证推导后续位置的状态的正确性。 下标的映射关系。 初始化虚拟节点
我们根据状态表示定义dp[i][j]表示s1[0,i-1]和s2[0,j-1]区间中所有公共子序列ASCII的最大和可以将第一行和第一列虚拟节点位置表示为空串的意义统一状态表示。
接下来初始化绿色位置的状态。 初始化第一行 此时i0表示s1为空串公共子序列不存在所以对应ASCII值应该为0。将第一行全部初始化为0。 初始化第一列 此时j0表示s2为空串公共子序列不存在所以对应ASCII值应该为0。将第一列全部初始化为0。
下标映射关系 此时定义dp[i][j]表示s1[0,i-1]和s2[0,j-1]区间中所有公共子序列ASCII的最大和。 dp中i对应s1的i-1位置dp中j对应s2的j-1位置。 如果在s1s2前面添加一个占位符就可以使得dp中ij继续映射s1s2中ij。 我们这里选择第一种解决办法。
填表顺序
根据状态转移方程 dp[i][j] max(dp[i][j - 1], dp[i - 1][j]);if (s1[i - 1] s2[j - 1])dp[i][j] max(dp[i][j], dp[i - 1][j - 1] s1[i - 1]);
我们知道在推导ij位置的状态时需要用到ij-1i-1ji-1j-1以及s1i-1和s2j-1的值。 固定i改变j i的变化需要从小到大由于需要用到ij-1位置的状态所以j的变化需要从小到大。 固定j改变i j的变化需要从小到大由于需要用到i-1j位置的状态所以j的变化需要从小到大。
返回值
根据状态表示定义dp[i][j]表示s1[0,i-1]和s2[0,j-1]区间中所有公共子序列ASCII的最大和。
结合题目要求我们需要找到s1[0,m-1]和s2[0,n-1]区间中所有公共子序列ASCII的最大和。然后返回”s1s2中ASCII和“ - 2*dp[m][n]
代码实现 class Solution {
public:int minimumDeleteSum(string s1, string s2) {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int m s1.size(), n s2.size();vectorvectorint dp(m 1, vectorint(n 1));for (int i 1; i m; i)for (int j 1; j n; j) {dp[i][j] max(dp[i][j - 1], dp[i - 1][j]);if (s1[i - 1] s2[j - 1])dp[i][j] max(dp[i][j], dp[i - 1][j - 1] s1[i - 1]);}int sum 0; // 统计元素和for (auto s : s1)sum s;for (auto s : s2)sum s;return sum - dp[m][n] - dp[m][n];}
};
718. 最长重复子数组 - 力扣LeetCode 题目解析 状态表示
对于两个字符串之间的dp问题我们的一般的思考方式如下 选取第一个字符串的[0,i]区间以及第二个字符串的[0,j]区间当成研究对象结合题目要求来定义状态表示。 然后根据两个区间上最后一个位置的状况进行分类讨论从而确定状态转移方程。
根据上述思路我们很容易可以定义这样一个状态表示
dp[i][j]表示以nums1中i位置元素结尾、nums2中j位置元素结尾的所有公共子数组中最长的公共子数组长度值。
状态转移方程 如果nums1[i]nums2[j] 因为是子数组所以如果以nums1[i]、nums2[j]为结尾的公共子数组长度大于等于2此时一定包括nums1[i-1]、nums[j-1]元素。此时dp[i][j]dp[i-1][j-1]1。 如果nums1[i]nums2[j] 此时不存在以nums1[i]、nums2[j]为结尾的公共子数组所以长度为0。 故状态转移方程为 if (nums1[i] nums2[j]) dp[i][j] dp[i - 1][j - 1] 1, ret max(ret, dp[i][j]);初始化 根据状态转移方程我们知道在推导ij位置的状态时可能需要用到i-1j-1位置的状态。
所以蓝色位置的状态会发生越界此时推导ij位置的状态时没有前驱值所以我们需要初始化这些位置的状态。
或者我们可以添加虚拟节点即多添加一行和一列使这些虚拟节点成为蓝色位置的前驱这样就不用初始化蓝色位置的值而变为初始化虚拟节点即可。
这样做的好处是虚拟结点的初始化可能比蓝色部分位置状态的初始化要简便许多。 添加虚拟结点后状态表示和状态转移方程会发生改变即
dp[i][j]表示以nums1中i-1位置元素结尾、nums2中j-1位置元素结尾的所有公共子数组中最长的公共子数组长度值。 if (nums1[i - 1] nums2[j - 1]) dp[i][j] dp[i - 1][j - 1] 1, ret max(ret, dp[i][j]); 添加虚拟节点后有两点注意事项 初始化虚拟节点必须保证推导后续位置的状态的正确性。 下标的映射关系。 初始化虚拟节点
我们根据状态表示dp[i][j]表示以nums1中i-1位置元素结尾、nums2中j-1位置元素结尾的所有公共子数组中最长的公共子数组长度值可以将第一行和第一列虚拟节点位置表示为空串的意义统一状态表示。
接下来初始化绿色位置的状态。 初始化第一行 此时i0表示nums1为空串公共子数组不存在所以对应长度值应该为0。将第一行全部初始化为0。 初始化第一列 此时j0表示nums2为空串公共子数组不存在所以对应长度值应该为0。将第一列全部初始化为0。
下标映射关系 此时定义dp[i][j]表示nums1[0,i-1]和nums2[0,j-1]区间中所有公共子序列ASCII的最大和。 dp中i对应nums1的i-1位置dp中j对应nums2的j-1位置。 如果在nums1nums2前面添加一个占位符就可以使得dp中ij继续映射nums1nums2中ij。 我们这里选择第一种解决办法。
填表顺序
根据状态转移方程我们知道在推导ij位置的状态时可能需要用到i-1j-1位置的状态。 固定i改变j 此时i的变化需要从小到大j的变化可以从小到大也可以从大到小。 固定j改变i 此时j的变化需要从小到大i的变化可以从小到大也可以从大到小。
返回值
dp[i][j]表示以nums1中i-1位置元素结尾、nums2中j-1位置元素结尾的所有公共子数组中最长的公共子数组长度值。
结合题目意思我们需要返回所有情况下最长的公共子数组的长度值所以我们需要遍历dp表找到最大的值然后返回。
代码实现 class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {int m nums1.size(), n nums2.size();vectorvectorint dp(m 1, vectorint(n 1));int ret 0;for (int i 1; i m; i)for (int j 1; j n; j)if (nums1[i - 1] nums2[j - 1]) dp[i][j] dp[i - 1][j - 1] 1, ret max(ret, dp[i][j]);return ret;}
};
结尾
今天我们学习了动态规划的思想动态规划思想和数学归纳法思想有一些类似动态规划在模拟数学归纳法的过程已知一个最简单的基础解通过得到前项与后项的推导关系由这个最简单的基础解我们可以一步一步推导出我们希望得到的那个解把我们得到的解依次存放在dp数组中dp数组中对应的状态就像是数列里面的每一项。最后感谢您阅读我的文章对于动态规划系列我会一直更新如果您觉得内容有帮助可以点赞加关注以快速阅读最新文章。 最后感谢您阅读我的文章希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点请随时在评论区留言。 同时不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中我将继续探讨这个话题的不同方面为您呈现更多深度和见解。 谢谢您的支持期待与您在下一篇文章中再次相遇
