珠海网站建设 骏域网站,网站权重传递,wordpress自定义上传路径,wordpress捐回文子串
回文子串这里的递推式不太一样#xff0c;dp[i] 和 dp[i-1] #xff0c;dp[i 1] 看上去都没啥关系。所以要回归到回文的定义
而我们发现#xff0c;判断一个子字符串#xff08;字符串下标范围[i,j]#xff09;是否回文#xff0c;依赖于#xff0c;子字符串…回文子串
回文子串这里的递推式不太一样dp[i] 和 dp[i-1] dp[i 1] 看上去都没啥关系。所以要回归到回文的定义
而我们发现判断一个子字符串字符串下标范围[i,j]是否回文依赖于子字符串下标范围[i 1, j - 1] 是否是回文。
布尔类型的dp[i][j]表示区间范围[i,j] 注意是左闭右闭的子串是否是回文子串如果是dp[i][j]为true否则为false。
画矩阵图的原因就是为了推断遍历的方向
class Solution {
public:int countSubstrings(string s) {vectorvectorbool dp(s.size(),vectorbool(s.size(),false));int result0;for(int is.size()-1;i0;i--){for(int ji;js.size();j){if(s[i]s[j]){if(j-i1){result;dp[i][j]true;}else if(dp[i1][j-1]){result;dp[i][j]true;}}}}return result;}
};最长回文子序列
回文子序列可以是不连续的
dp[i][j]字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。 动态规划复习
背包问题
arrangement 排列 有顺序 combination 组合 无顺序 就是分成几个组的问题 排列要先遍历背包再遍历物品 组合就先遍历物品再遍历背包就能保证一种组合只出现一次 完全背包复习
打家劫舍问题
会有一道树形dp问题复习
股票问题
涉及到多个状态的动态规划如何实现复习
https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93%E7%AF%87.html#%E5%8A%A8%E8%A7%84%E7%BB%93%E6%9D%9F%E8%AF%AD
