贵州省建设厅建筑官方网站,徽章设计制作小程序,浙江省建筑培训网,长春宣传片拍摄动态规划
动态规划就像是解决问题的一种策略#xff0c;它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题#xff0c;并将每个小问题的解保存起来。这样#xff0c;当我们需要解决原始问题的时候#xff0c;我们就可以直接利…动态规划
动态规划就像是解决问题的一种策略它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题并将每个小问题的解保存起来。这样当我们需要解决原始问题的时候我们就可以直接利用已经计算好的小问题的解而不需要重复计算。 动态规划与数学归纳法思想上十分相似。
数学归纳法 基础步骤base case首先证明命题在最小的基础情况下成立。通常这是一个较简单的情况可以直接验证命题是否成立。 归纳步骤inductive step假设命题在某个情况下成立然后证明在下一个情况下也成立。这个证明可以通过推理推断出结论或使用一些已知的规律来得到。
通过反复迭代归纳步骤我们可以推导出命题在所有情况下成立的结论。 动态规划 状态表示 状态转移方程 初始化 填表顺序 返回值
数学归纳法的基础步骤相当于动态规划中初始化步骤。
数学归纳法的归纳步骤相当于动态规划中推导状态转移方程。
动态规划的思想和数学归纳法思想类似。 在动态规划中首先得到状态在最小的基础情况下的值然后通过状态转移方程得到下一个状态的值反复迭代最终得到我们期望的状态下的值。 接下来我们通过三道例题深入理解动态规划思想以及实现动态规划的具体步骤。
1745. 分割回文串 IV - 力扣LeetCode 题目解析 状态表示
状态表示通常由经验题目要求得到
经验一般指以某个位置为结尾或者以某个位置为开始。
我们需要判断ij子数组是否属于回文子数组可以定义dp[i][j]表示ij子数组是否属于回文子数组。
状态转移方程
我们希望ij位置的状态能够通过其他位置的状态推导出来。
针对于ij位置的状态进行分析。 如果nums[i]nums[j] 如果ij子数组只有一个元素即ij 只有一个元素属于回文子数组情况故dp[i][j]true。 如果ij子数组只有两个元素即i1j 此时符合回文子数组的定义故dp[i][j]true。 如果ij子数组有3个或3个以上的元素即i1j, 此时如果(i1,j-1)子数组可以构成回文子数组那么ij子数组就可以构成回文子数组。 故dp[i][j]dp[i1][j-1]。 如果nums[i]!nums[j] 此时不可能构成回文子数组所以dp[i][j]false。 对上述情况进行合并和简化
如果我们对所有位置状态初始化为false我们就只需要判断nums[i]nums[j]的情况
此时的状态转移方程为 if(s[i]s[j]){dp[i][j] i 1 j ? dp[i 1][j - 1] : true;}
初始化
根据状态转移方程我们知道推导ij位置的状态时可能需要用到dp[i1][j-1]位置的状态 如果i1j,此时需要保证i1j-1对应下标不会越界并且此时i1j-1位置状态已经填写完毕。 先考虑填表顺序我们知道i介于0n-1之间j介于in-1之间所以i1介于1n之间且i1j所以i1介于1n-1之间i1不会越界。
又j介于in-1之间j-1介于i-1n-2之间又j-1i所以j-1也不会越界。 要保证此时i1j-1位置状态已经填写完毕只需要控制填报顺序即可。
所以我们需要初始化所有位置状态为false即可也就是在状态转移方程中分析的初始化。
填表顺序
根据状态转移方程我们知道推导ij位置的状态时可能需要用到dp[i1][j-1]位置的状态 所以在填写ij位置状态时需要保证i1j-1位置状态已经填写完毕。 如果固定i填写j 那么i的变化一定要从大到小此时当我们填写ij位置的状态时i1位置的状态已经填写完毕所以j的变化可以从大到小也可以从小到大。 如果固定j填写i 那么j的变化一定要从小到大此时当我们填写ij位置的状态时j-1位置的状态已经填写完毕所以i的变化可以从大到小也可以从小到大。 如果我们选择固定i填写j得到 for(int in-1;i0;i--){for(int ji;jn-1;j){}}
返回值
dp[i][j]表示ij子数组是否属于回文子数组。
dp状态的填写只完成了第二步的工作即快速判断ij子数组是否为回文子数组。
还有一步就是使ab遍历所有情况。
如果有一种情况三部分都是回文子数组就返回true否则就返回false。
代码实现 class Solution {
public:bool checkPartitioning(string s) {int n s.size();vectorvectorbool dp(n, vectorbool(n));for (int i n - 1; i 0; i--)for (int j i; j n; j)if (s[i] s[j])dp[i][j] i 1 j ? dp[i 1][j - 1] : true;for (int i 1; i n - 1; i)for (int j i; j n - 1; j)if (dp[0][i - 1] dp[i][j] dp[j 1][n - 1])return true;return false;}
};
132. 分割回文串 II - 力扣LeetCode 题目解析 状态表示
状态表示通常由经验题目要求得到
经验一般指以某个位置为结尾或者以某个位置为开始。
我们很容易可以定义这样一个状态表示定义dp[i]表示在0i区间上的字符串最少的分割次数。
状态转移方程
我们针对于最后一个位置的状态进行分析看看i位置状态能不能由其他位置的状态推导得出定义0ji那我们可以根据ji位置上的子串是否是回文串分成下面两种情况 如果ji可以构成回文串 i位置的状态就等于j-1位置上的状态1即dp[i]dp[j-1]1。 如果ji不能构成回文串 此时j的位置不需要考虑。
因为dp[i]要的是最小的分割次数所以j需要遍历0~i-1。 因为我们需要快速判断ji位置是否属于回文字符串所以我们可以先创建一个dp表dp[i][j]表示ij字符串是否构成回文字符串。用来存储是否可以构成回文字符串的信息。 根据上述分析我们知道要推导i位置的状态可能需要用到j-1位置的状态。
所以i的变化应该是从小到大即0~n-1。
令j-10得j1只有j1的时候才不会越界。所以我们需要控制j介于1i之间。
独立判断0i这种情况。
所以状态转移方程为 for (int i 0; i n; i) {if (isPal[0][i])dp[i] 0;else {for (int j 1; j i; j)if (isPal[j][i])dp[i] min(dp[i], dp[j - 1] 1);}}
初始化
带入最初始的推导即i0发现dp[i] 可以正常推导而后续的状态都可以根据前面已经推导的状态进行推导得出所以不需要进行初始化。
填表顺序
从左往右
返回值
dp[i]表示在0i区间上的字符串最少的分割次数。
题目要求我们找到0n-1区间上的字符串最少的分割次数
所以返回dp[n-1]即可。
代码实现 class Solution {
public:int minCut(string s) {int n s.size();vectorvectorbool isPal(n, vectorbool(n));for (int i n - 1; i 0; i--)for (int j i; j n; j)isPal[i][j] s[i] s[j] ? (i 1 j ? isPal[i 1][j - 1] : true): false;vectorint dp(n, INT_MAX);for (int i 0; i n; i) {if (isPal[0][i])dp[i] 0;else {for (int j 1; j i; j)if (isPal[j][i])dp[i] min(dp[i], dp[j - 1] 1);}}return dp[n - 1];}
};
516. 最长回文子序列 - 力扣LeetCode 题目解析 状态表示
状态表示一般通过经验题目要求得到
经验一般指以某个位置为结尾或者以某个位置为开始。
题目要求我们找回文子序列根据以前的经验和回文有关的问题我们的状态表示研究的对象一
般都是选取原字符串中的一段区域[i,j]内部的情况来研究。
所以我们可以定义dp[i][j]表示s字符串[i,j]区间内所有子序列中最长的回文序列长度。
状态转移方程
我们针对于最后一个位置的状态进行分析看看i位置状态能不能由其他位置的状态推导得出。 如果紫色的字符串可以构成回文串那么我们在紫色字符串两端添加相同的蓝色元素整个字符串同样可以构成回文串。
根据这种思维我们可以根据ij两个位置的元素是否相等进行分析。 如果s[i]s[j] 那么[ij]区间上的最长回文子序列应该是 [i1,j-1] 区间上的最长回文子序列首尾加上s[i],s[j]两个元素此时dp[i][j]dp[i1][j-1]2。 如果s[i]!s[j] 说明[i,j]区间上的回文子序列不可能同时取到i,j两个位置上的元素。 如果i位置元素不取 此时[i,j]区间上的最长回文子序列的长度应该是[i1,j]区间上的最长回文子序列的长度。即dp[i][j]dp[i1][j]。 如果j位置元素不取, 此时[i,j]区间上的最长回文子序列的长度应该是[i,j-1]区间上的最长回文子序列的长度。即dp[i][j]dp[i][j-1]。 第二种情况下dp中存储的是最长的回文子序列的长度所以dp[i][j]max(dp[i1][j],dp[i][j-1])。
综上所述状态转移方程为
s[i] s[j] 时: dp[i][j] dp[i 1][j - 1] 2 s[i] ! s[j] 时: dp[i][j] max(dp[i][j - 1],dp[i 1][j])
初始化
根据状态转移方程我们知道想要推导ij位置的状态可能需要用到i1j-1ij-1i1j位置上的状态。
我们先判断填表顺序 如果固定i改变j 那么i的变化一定从大到小因为可能用到ij-1位置的状态所以j的变化需要从小到大。 如果固定j改变i 那么j的变化一定从小到大因为可能用到i1j位置的状态所以i的变化需要从大到小。 所以我们可以得到完整的状态转移方程 for (int i n - 1; i 0; i--){dp[i][i] 1; for (int j i 1; j n; j){if (s[i] s[j])dp[i][j] dp[i 1][j - 1] 2;elsedp[i][j] max(dp[i 1][j], dp[i][j - 1]);}} 我们把最初迭代情况带入迭代代码中即in-1jn此时得到dp[n-1][n-1]1。
而后续的状态都可以根据前面的状态推导得出所以我们不需要进行初始化。
填表顺序 如果固定i改变j 那么i的变化一定从大到小因为可能用到ij-1位置的状态所以j的变化需要从小到大。 如果固定j改变i 那么j的变化一定从小到大因为可能用到i1j位置的状态所以i的变化需要从大到小。
返回值
dp[i][j]表示s字符串[i,j]区间内所有子序列中最长的回文序列长度。
根据题目要求我们需要得到[0,n-1]区间内所有子序列中最长的回文子序列长度。
所以返回dp[0][n-1]。
代码实现 class Solution {
public:int longestPalindromeSubseq(string s) {int n s.size();vectorvectorint dp(n, vectorint(n)); for (int i n - 1; i 0; i--){dp[i][i] 1; for (int j i 1; j n; j){if (s[i] s[j])dp[i][j] dp[i 1][j - 1] 2;elsedp[i][j] max(dp[i 1][j], dp[i][j - 1]);}}return dp[0][n - 1];}
};
结尾
今天我们学习了动态规划的思想动态规划思想和数学归纳法思想有一些类似动态规划在模拟数学归纳法的过程已知一个最简单的基础解通过得到前项与后项的推导关系由这个最简单的基础解我们可以一步一步推导出我们希望得到的那个解把我们得到的解依次存放在dp数组中dp数组中对应的状态就像是数列里面的每一项。最后感谢您阅读我的文章对于动态规划系列我会一直更新如果您觉得内容有帮助可以点赞加关注以快速阅读最新文章。 最后感谢您阅读我的文章希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点请随时在评论区留言。 同时不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中我将继续探讨这个话题的不同方面为您呈现更多深度和见解。 谢谢您的支持期待与您在下一篇文章中再次相遇
