核心思想：
将问题分解为重叠的子问题，并储存子问题的解（使用字典、数组或哈希表），避免重复计算，从而提高效率。
题目特点：重叠子问题（特殊地，是最优子结构）
比如：斐波那契数列问题中，递归求F(5)，需要多次计算F(3)；
最短路径问题中，若从A到C的最优路径包含B，则A到B和B到C也必然是最优的。
两种实现方式：
自顶向下（递归+储存记忆，将大问题逐步分解，子问题的解储存在字典里）：
class Solution(object):
# 把momory作为类属性
memory = {}
def fib(self, n):
# 如果已经在记忆里储存，则直接返回，不用再重复计算
if n in self.memory:
return self.memory[n]
if n<=1:
return n
self.memory[n] = self.fib(n-1)+self.fib(n-2)
return self.memory[n]自底向上（迭代+储存记忆，先解决小问题再解决大问题，小问题的解储存在数组里）：
class Solution(object):
def fib(self, n):
"""
:type n: int
:rtype: int
"""
dp = [0,1] # 动态规划数组，初始值相当于递归里遇到终止条件能直接返回的值
for i in range(2,n+1):
dp.append(dp[i-1]+dp[i-2])
return dp[n]解题步骤：
1、定义状态（dp[i]表示什么）
2、写状态转移方程（由局部最优一直推到全局最优，所以从初始截断到当前位置来考虑即可，后面的先不管）
3、确定初始状态（起码两个）
3、用递归or迭代解题
比如：“打家劫舍”求数组中不相邻元素组合，使值的和最大
（1）定义状态：设dp[i]表示从第0到第i个中元素组合的最优解；
（2）状态转移方程：
则可以分类讨论：目前最优解要不要加上dp[i]这个元素，
即是取dp[i-1]还是dp[i-2]+nums[i]，
比较两者取较大值就行。
得方程，dp[i] = max（dp[i-1]，dp[i-2]+nums[i]）
（3）初始条件：dp[0]=1，dp[1]=max（nums[0]，nums[1]）
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n==1:
return nums[0]
dp = [nums[0],max(nums[0],nums[1])] #注意基础条件里，nums[1]不一定有，需要分类讨论
for i in range(2,n):
dp.append(max(dp[i-1],dp[i-2]+nums[i]))
return dp[n-1]删除并获得点数
class Solution(object):
def deleteAndEarn(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 转换思维：统计每个数字的总点数，生成一个数组sums[x] = x*count(x)
# 接着，类似于打家劫舍问题，取不相邻的元素，使元素的和最大
# 设dp[i]为遍历到i的最优解，dp[i] = max(dp[i-1],dp[i-2]+sums[i])
# 生成sums数组（先找到nums[i]的最大值，用它作为sums数组的最大边界）
max_num = max(nums)
sums = [0] * (max_num+1) #初始化
for num in nums:
sums[num] += num
# 动态规划求解
if len(sums) == 1:
return 0
dp = [0,sums[1]]
#dp = [sums[0],max(sums[0],sums[1])]
for i in range(2,len(sums)):
dp.append(max(dp[i-1],dp[i-2]+sums[i]))
return dp[len(sums)-1]优化技巧：
1、滚动变量替代dp数组
class Solution(object):
def rob(self, nums):
n = len(nums)
if n==1:
return nums[0]
# 滚动变量优化空间，不需要整个dp数组
pre, cur = nums[0],max(nums[0],nums[1]) #dp = [nums[0],max(nums[0],nums[1])]
for i in range(2,n):
pre, cur = cur, max(cur, pre+nums[i])
#dp.append(max(dp[i-1],dp[i-2]+nums[i]))
return cur
可以理解为先计算temp = max(cur, pre + nums[i])，然后让pre=cur，再让cur=temp。
最长回文子串：
（1）定义状态：dp[i][j]表示字符串从第i个字符到第j个字符是否为回文字符串。
（2）状态转移方程：
往子问题方向拆分——如果dp[i][j]是回文子串，那么两端的字符必定相等，而且中间的字符串（如果有）也应该是回文子串。即
dp[i][j] = （s[i]==s[j]）&&（（j==i+1）or dp[i+1][j-1]）
（3）初始条件：
只有一个字符，dp[i][i]=True
则，可以总结出：dp[i][i]=True
dp[i][j] = （s[i]==s[j]）&& （（j==i+1）or dp[i+1][j-1]）
迭代法的状态转移：判断首尾相等后，每个位置的状态和它的左下角的状态有关
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s)
if n<=1:
return s
# 初始化动态规划表
dp = [[False]*n for _ in range(n)]
# 初始条件：所有长度为1的子串都是回文
for i in range(n):
dp[i][i] = True
max_len = 1
start = 0 #追踪最长回文子串的起始位置
# dp[i][j] = （s[i]==s[j]）&& （（j==i+1）|| dp[i+1][j-1] ）
for j in range(1,n): #右指针，子区间的右边界，从1到n-1
for i in range(0,j): #左指针，子区间的左边界，从0到j-1
if s[i]==s[j]: #如果左右边界相等
if (j==i+1) or (dp[i+1][j-1]): #如果没有中间部分或者中间部分也是回文子串
dp[i][j] = True #标记
length = j-i+1
if length>max_len: #看需不需要更新
max_len=length
start=i
return s[start:start+max_len]
[False] * n借助列表乘法操作，将包含单个False的列表重复n次，从而生成一个长度为n且所有元素都为False的一维列表。
_是 Python 里的一个惯用变量名，通常用于表示一个临时的、不会被使用的变量。
s[start:start+max_len]是 Python 中用于字符串切片操作（左闭右开）的表达式。它的作用是从字符串s中提取一个子字符串，该子字符串从索引start开始，到索引start + max_len - 1结束。
高阶理解：
（有向无环图，状态可转移；空间换时间）
将节点抽象，关系用边表示，用人脑简单求一次拓扑排序，
如果有环，则一定不是动态规划
也和数据范围有关，数据量太大，无法映射到数组中，就不是动态规划
