Dynamic programming
相关概念
把原问题分解为相对简单的子问题，适用于某问题有很多重叠子问题。
每⼀个状态⼀定是由上⼀个状态推导出来的（考虑状态之间的关系式）
- 确定 数组及下标含义
- 确定递推公式
- 数组如何初始化
算法应用
最优化问题：寻找最大或最小值、总和、路径等。
最长公共子序列
Longest common subsequence, LCS,
Leetcode LCR 095
最长回文子串
输入：s = “babad”；输出：“bab”（“aba” 同样符合题意）
动态规划
表示字符串从第 到 个字母构成的子字符串
如果 是回文串，则也一定是回文串
中心拓展
枚举回文子串的中心位置
可能是一共字符
可能是两个相邻字符
背包问题
有一个固定容量的背包和一组物品，每个物品有自己的重量和价值。问题的目标是选择一些物品放入背包中，使放入背包的物品的总价值最大化，同时不能超过背包的容量限制。