代码随想录算法训练营day51|动态规划part13

回文子串

回文子串这里的递推式不太一样，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) {vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));int result=0;for(int i=s.size()-1;i>=0;i--){for(int j=i;j<s.size();j++){if(s[i]==s[j]){if(j-i<=1){result++;dp[i][j]=true;}else if(dp[i+1][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