利用历史信息，解决有最优子结构的问题，最优子结构即：全局最优解能够通过局部最优解推导出来；与后续状态无关；具有重复子问题的特性
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1：
输入：cost = [10, 15, 20] 输出：15 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
和青蛙跳阶梯不一样，如果只有一阶，可以直接跳两阶跨过第一阶，并且由于第二阶的花费未定义，所以为0
- 一次交易：
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票
用一个2*n的数组表示当天的盈利，第一个状态表示买当天的股票得到的最大盈利；第二个状态表示卖掉当天的股票得到的最大盈利。状态转移的情况：
-
今天持股
- 昨天持股：啥也没干
$dp[i-1][0]$
- 昨天不持股：卖出去了
$dp[i-1][1]+prices[i]$
- 昨天持股：啥也没干
-
今天不持股：
- 昨天持股：买入股票
- 只能进行一次交易，所以：$-prices[i]$
- 昨天不持股：啥也没干
$dp[i-1][1]$
- 昨天持股：买入股票
-
多次交易
-
今天持股
- 昨天持股：啥也没干
$dp[i-1][0]$
- 昨天不持股：卖出去了
$dp[i-1][1]+prices[i]$
- 昨天持股：啥也没干
-
今天不持股：
- 昨天持股：买入股票
$dp[i-1][0]-prices[i]$
- 昨天不持股：啥也没干
$dp[i-1][1]$
- 昨天持股：买入股票
-
只能两次交易，且第二次交易前必须卖掉前一次交易的股票
需要定义五个状态，在这五个状态条件下每天可以有买和卖操作：
状态数组为：n*5的数组，$dp[i][j]$表示第i天第j个状态剩下的现金
- 无操作
- 第一次买入
- 第一次卖出
- 第二次买入
- 第二次卖出
状态转移：
- 今天无操作：
- 昨天无操作：$dp[i-1][0]$
- 今天第一次买入的状态（今天的状态为第一次买入的状态不代表是今天的操作，有可能是延续过去的动作）：
- 昨天无操作：$dp[i-1][0]-prices[i]$
- 延续昨天买入的状态：$dp[i-1][1]$
- 今天第一次卖出的状态：
- 昨天第一次买入：$dp[i-1][1]+prices[i]$
- 延续昨天第一次卖出的状态：$dp[i-1][2]$
- 今天第二次买入的状态：
- 昨天第一次卖出了：$dp[i-1][2]-prices[i]$
- 延续昨天第二次买入的状态：$dp[i-1][3]$
- 今天第二次卖出的状态：
- 昨天第第二次买入：$dp[i-1][3]+prices[i]$
- 延续昨天第二次卖出的状态
初始状态：
-
第一天无操作：盈利0
-
第一天第一次买入：-prices[0]
-
第一天第一次卖出：盈利0
-
第一天第二次买入：(等价于今天买了又卖，然后又上手买了一次)-prices[0]
-
第一天第二次卖出：盈利0
-
冷冻期
当天卖出股票之后属于冷冻期状态，第二天不能买入股票了
定义三种状态：
- 今天持有股票，既然持有了，肯定是能买到的，不用考虑冷冻期问题
- 昨天就是持有的状态
- 今天现买的
- 今天不持有股票，属于冷冻期状态，不持有且在冷冻期只能是今天刚卖出去
- 昨天持有股票的状态，今天卖出去了
- 今天不持有股票，不属于冷冻期状态，既然不持有股票，说明今天没做任何操作，如果今天买入股票了，那么肯定是持有股票状态；如果今天卖出股票了，肯定是冷冻期状态。这么看来，说明昨天就不持有股票；如果昨天持有股票，那么今天不持有股票的状态只能是今天操作过了，但是前面说了今天没做任何操作，所以昨天是不持有股票状态
- 延续昨天不持有股票，但是不属于冷冻期的状态
- 昨天是冷冻期，今天刚解封
给定两个字符串，判断最长公共的子串/子序列
最长公共子串：要求公共部分要连续出现在两个字符串中
最长公共子序列：不要求连续，只需要是按照字符串的顺序出现的即可
二维dp，$dp[0][0]$表示空串和空串，$dp[i][j]$表示str1[:i]和str2[:j]的最长公共子串/子序列
如果str1[i-1]和str2[j-1]相同，那么$dp[i][j]= dp[i-1][j-1]+1$
最长公共子串匹配很严格，如果两个子串最后一个字母不同，那么就不存在最长公共子串；最长公共子序列不是很严格，如果最后两个字母不同，还可以检查str1[:i-1]和str2[:j]以及str1[:i]和str2[:j-1]的最长公共子序列，并且取两者最大的，即：$dp[i][j]=max(dp[i-1][j], dp[i][j-1])$
-
如何得到最长公共子串/序列的字符串？
根据dp数组倒推，$dp[m][n]$表示题目要求的最长公共子串/序列的长度，如果是子串，就找dp中值最大的位置$dp[i][j]=l$，那么最长公共子串为$s1[j-l:j]$;如果是最长公共子序列，就根据dp数组倒推，定义两个指针分别指向字符串最后一个字符，$dp[i][j]$如果$s1[i-1]=s[j-1]$，就把字符记录下来，然后两个指针都往前一步；如果不相等，就找$dp[i-1][j]和dp[i][j-1]$中最大的，指针就往最大的那个方向跑，直到遍历完两个字符串，时间复杂度$O(n^2)$
-
最大子序和：
- 状态定义：dp[i]表示arr[:i]的最大子序和，即以arr[i]为结尾的连续子数组最大子序和
- 状态转移：
- dp[i] = max(dp[i-1]+arr[i], arr[i])
- 由于存储的状态要求是连续子数组，因此每个位置都是局部最优值，需要全局变量保存全剧最优值
- 初始状态：
- dp[0]=0，空数组为0
- dp[1]=arr[0]，一个元素的数组没得选，就是它本身的值
-
最大子数组乘积
- 状态定义：与求和不同的是，乘积由于有正负号的关系，只用一个数组保存最大的数可能会漏解，比如：[2, 1, -7, -8]，明显最大的子数组乘积是所有数相乘，但是按照前面保留局部最大值的话，负数就会被排除，得不到最优解。此时应该保存两个dp，一个求解局部最大值，一个求解局部最小值
- 状态转移
- Max[i]=max(Max[i-1]*arr[i], Min[i-1]*arr[i], arr[i])
- Min[i]=min(Max[i-1]*arr[i], Min[i-1]*arr[i], arr[i])
- 最后返回值是最大值dp的结果，最小值dp只是保留负数的状态
- 初始状态：
- Max[0]=Min[0]=0，空子数组为0
- Max[1]=Min[1]=arr[0]，只有一个元素的子数组没有选择
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释： 2 3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
- 状态定义：
- 二维dp，$dp[i][j]$表示从顶端出发到第i层第j个元素的最小路径
- 状态转移：
- 需要自定义边界，当上一层的点在两边时，只有一条路径；不在两边时，有两条路径
$dp[i][0]=dp[i-1][0]+triangle[i][0]$ $dp[i][i]=dp[i-1][i-1]+triangle[i][i]$
- 有两条路径的就需要从中选择最小的路径了
$dp[i][j]=min(dp[i-1][j], dp[i-1][j-1])+triangle[i][j]$
- 需要自定义边界，当上一层的点在两边时，只有一条路径；不在两边时，有两条路径
- 最优解：
- 最优解即最后一层dp的最小值：min(dp[-1])
- 初始状态：
$dp[0][0]=triangle[0][0]$
最小路径和与三角形最小路径和类似，也需要注意边界上只有一条路
不同路径类似，定义状态为$dp[i][j]$表示从原点出发到$arr[i][j]$的路径条数
不同的路径II中多了障碍物，状态和不同的路径I类似，只不过当$arr[i][j]$为障碍物时，路径条数为0
-
状态定义：dp[i]表示偷arr[:i+1]里面的屋子的最大收益
-
状态转移：
- 偷到第i间屋子，第i间屋子有两个选择，偷或者不偷
- 如果偷第i间屋子，那么前面一间屋子就不能投，只能从dp[i-2]转移而来，即dp[i-2]+arr[i]
- 如果不偷第i间屋子，那么就是从前面一间屋子转移而来，dp[i-1]
- 两者取最大收益
- 偷到第i间屋子，第i间屋子有两个选择，偷或者不偷
-
初始状态：
- 没有屋子可以偷，收益为0
- 第1间屋子只能偷这一间
- 只有一间屋子直接返回arr[0]
-
打家劫舍II要求房子围成了一圈，这就意味着首尾不能同时偷，此时应该分成两部分，arr[:l-1]和arr[1:]来偷，这样就不用判断是否首尾同时偷了，同时最优解是两者取最大值
给定一定面额的零钱arr，要求将给定的钱兑换成数量最少的零钱
- 声明dp数组，dp[i]表示给定i元，找给的数量最少的钱
- 状态转移
- 遍历各个面额的钱，如果找的开就尝试找零钱，找完后就相当于钱的数量多了一张，剩下的钱就去dp数组中查表剩下的钱怎么找最少
- dp[i] = min(dp[i], dp[i-amount]+1)
- 最后dp[amount]就是所求的结果
- 遍历各个面额的钱，如果找的开就尝试找零钱，找完后就相当于钱的数量多了一张，剩下的钱就去dp数组中查表剩下的钱怎么找最少
- 数组初始状态：由于是求最小值，所以给数组都赋值无穷大，便于多次求最小值
- 如果最后dp[amount]为无穷大，说明零钱找不开，直接返回-1
- 声明dp数组，状态$dp[i][j]$表示以i开头，j结尾的字符串是否为回文串
- 特殊地，这道题需要先按字符串长度遍历，将长度从短到长的顺序遍历，因为长的回文串的判断依赖于短的回文串
- 状态转移
- 如果当前字符串长度为1，那么他就是回文串
- 如果当前字符串长度为2，并且两个字符串是相同的，那么它是回文串
- 如果长度超过2了，那么要想成为回文串，其前后两个字符必须相同，而且中间的字符串也必须是回文串$dp[i+1][j-1]=1$
- 初始状态：这里初始化全部放到循环内了，不需要初始化
- 要想拿到最长回文串，就可以保存一个全局最长的回文串长度，如果碰到更长的回文串长度，就更新长度和这个回文串
- 状态定义：dp[0]表示空串，dp[i]表示s[:i]是否能被拆分
- 状态转移：
- 遍历前面的状态，s[:i]，并且遍历后面的状态j，即[i+1, n+1)，如果前面的单词s[:i]可拆分并且后面的单词s[i+1:j]在词典中，那么dp[j]也是可拆分的
- 初始状态：
- dp[0]为空串，默认是可拆分的
- 状态定义：一维dp，dp[i]表示nums[:i]有多少种翻译方式
- 状态转移：
- 如：'121'有三种翻译方法，'1 2 1'、12 1'和'1 21'，当某一位单独翻译时，其可翻译的方法和前面nums[:i-1]的方法一样，如：'12'和'12 1'可翻译的方法数一样；而当两位数作为翻译时，和前面两位的翻译方法数量一样，如：'1'和'1 21'，所以状态转移可以定义为
- dp[i] = dp[i-1]（如果当前位置不为'0'）
- dp[i] += dp[i-2]（如果nums[i-2:i]满足小于26，并且高位数字不为'0'，而且只有当i>1时才会有两个数字组合的情况）
- 特殊边界：
- '0'单独做一位时无法翻译，所以单独翻译一位的情况应该排除'0'
- '00'是不合法的，算作0
- '0'前面跟着'1'和'2'时是合法的，所以只有第二种情况才能让'0'有翻译方法
- 初始状态：
- 为了满足dp，设置dp[0]=1
def solve(nums ):
if len(nums)==0 or nums[0]=='0':
return 0
n = len(nums)
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
# 单独一位的，只有当当前位置是0时就不能翻译
if nums[i-1] != '0':
dp[i] = dp[i-1]
# 10和20属于这种情况，当然还得排除'00'这种情况
if i > 1 and nums[i-2] != '0' and int(nums[i-2:i]) <= 26:
dp[i] += dp[i-2]
return dp[-1]