1. 1. 动态规划典型场景
a. 股票买卖，只允许交易一次
i. 遍历数组，计算当前最低价和当前最大盈利
ii. 时间复杂度n，空间复杂度1
b. 矩阵的最小和路径/带权值的最小路径和
i. 开mn数组，存储当前最优解
ii. 构arr[i][j]=min(arr[i-1][j],arr[i][j-1])+num[i][j];
c. 无序数组中的最长连续序列
i. 数组排序，开数组，初始化数组
ii. 构造状态转移方程
1. 1. 如果当前数等于上一个数加一，res[i]=res[i-1]+1;
2. 2. 如果当前数等于上一个数，res[i]=res[i-1];
3. 3. 其他情形，res[i]=1;
iii. 时间复杂度nlogn
d. 数组中的最长连续子序列
e. 连续子数组最大乘积
i. 开数组，包含当前的正最大，包含当前的负数最小，
ii. 构造转移函数
1. 1. 正最大max(上一个正最大当前，上一个负最小当前，当前)
2. 2. 负最小min(上一个正最大当前，上一个负最小当前，当前)
iii. 临时最大正值
iv. 时间复杂度n，空间复杂度2n
f. 数组中的最长无重复子串 (类似动态规划，实际并不是)
i. 开数组，以当前位置结束的无重复子串的长度
ii. 如果当前位置之前的位置结束的无重复子串中含有当前位置的元素，当前位置结束的子串从重复位置开始+1，如果不包含，num[i]=num[i-1]+1
iii. 临时最大长度
iv. 时间复杂度为n^2
g. 最长回文子串
i. 动态规划
1. 1. 开二位数组arr[n][n]，存储i开始，j结束的是否为回文数组
2. 2. 构造转移方程
a. i降序，j从i开始，升至n
b. 初始化对角线为true, 二维数组左下半部分不用
c. arr[i][j] =arr[i+1][j-1]是true同时字符串第i位等于第j位
d. 临时最大值
3. 3. 时间复杂度为n^2,但是中间结果有记录，其实会快很多
ii. 非动态规划
1. 1. 从头开始遍历字符串
2. 2. 判断以i,i为中心的回文字符串长度，I,i+1为中心的回文串长度
3. 3. 临时最大长度
4. 4. 复杂度n^2
h. 最长回文子序列
i. 类似最长回文子串，开数组arr[n][n],代表以ij起止的最长回文子序列的长度
1. 1. I反向遍历，j从i开始正遍历
2. 2. 如果i==j,arr[][]=1
3. 3. 如果j=i+1,如果相等为2，如果不等为1
4. 4. 其他情况
a. 如果str(i)=str(j),arr[][]=arr[i+1][j-1]+2
b. 如果不等，等于以下三片段的最大值
i. I到j-1;
ii. I+1到j;
iii. I+1到j-1；
5. 5. 记录临时最大值，每次比较
6. 6. 返回最大值
7. 7. 复杂度 n^2,数组只用一半，还是比较快的
i. 最长括号子串
i. 开数组arr[n]代表以n结尾的最长合法子串
ii. 构造转移方程
1. 1. 当前为)
2. 2. 如果arr[i-1]=0且num[i-1]为(,此时arr[i]=arr[i-2]+2
3. 3. 如果arr[i-1]=m 且num[i-1-m]为(,此时arr[i]=m+2+arr[i-m-2]
iii. 从位置1开始遍历子串，存储临时max
iv. 时间复杂度n, 空间复杂度为n
j. 最长递增子序列
i. 开数组
ii. 转移方程
iii. 存储中间结果
k. 剪绳子，求整数拆分后的数字的最大乘积
i. 开数组，每个位置存当前最大乘积
ii. Max(arr[2][arr[i-2],arr[3]arr[i-3])
iii. 复杂度 n^2
l. 跳到当前位置需要的最小步数
i. 0号位需要0步骤
ii. 从1号位开始遍历，1号位需要1步，当前步数最大可达right=A[0]号位置,初始化index=0；
iii. 计算当前位置开始，下一步最大可以走多远index=Math.max(index-1,A[i]);
iv. 当位置坐标大于当前最大可达位置时，需要步数+1，当前步数最大可达right=index+right
v. 最后返回A[n-1]
m. 01背包问题
i. 动态规划，开启dp数组，dp[n+1][m+1],m代表容量，n代表包的类型
ii. 初始化dp[0][j],dp[i][0]==0;
iii. 当i==1时，初始化背包大于第一个物品的size的格子为1，其余为0；
iv. 循环遍历，
1. 1. 当背包总容量小于当前物品时，a[i][j]=a[i-1][j]
2. 2. 当背包总容量大于当前物品时
a. dp[i][j]=math.max(不放当前物品的最大价值，放当前物品的最大价值)
b. dp[i][j]=math.max(dp[i-1][j], 当前物品价值+dp[i-1][j-当前物品重量])
n.
