动态规划专题
1连续子数组的最大和（最大子序和）
输入一个整型数组nums，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
定义dp[i]: 以nums[i]为结尾的子数组的最大值
dp[i] = max(dp[i-1]+nums[i], nums[i])
以nums[i]为结尾的子数组的最大值,要么是他自己（比如dp[i-1]是负数）,要么在前面子数组的基础上加上自己，形成更长的连续子数组
记录整个过程中的最大值，返回该最大值（注意：dp[i]只是定义为以nums[i]为结尾的子数组的最大值，所以dp[n-1]不一定是最大值）。
2爬楼梯
假设你正在爬楼梯。需要n（n是一个正整数）阶你才能到达楼顶. 每次可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼顶
定义dp[i]: 爬完i阶台阶共有dp[i]种方法
dp[i] = dp[i-1] + dp[i-2]
每次爬楼梯只有两种方法，要么爬1个台阶，要么爬2个台阶。所以如果要爬到i级台阶，要么从i-1级台阶上爬1阶上来，要么从i-2级台阶上爬2阶上来
返回dp[n]
3偷东西
小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组nums，计算在不触动警报装置的情况下，能够偷窃到的最高金额
定义dp[i]: "光顾"完前i个房屋后,能够偷到的最高金额
dp[i] = max(dp[i-2]+nums[i], dp[i-1])
对于第i个房屋，有2种选择。偷或不偷。偷：偷得的金钱加上"光顾"完i-2房屋时的偷窃金额，不偷：光顾"完i-1房屋的偷窃金额
返回dp[n-1]
类似的题目:按摩师，在每次预约服务之间要有休息时间，因此不能接受相邻的预约，求总预约时间最长
变种1：房屋不是一排，而是围成了一个圈。也就是第一个房子和最后一个房子也是相邻的。
计算2种情况：1）nums[0...n-2] 2）nums[1...n-1]。返回两者较大值即可。
变种2：房屋排列成二叉树的形式，也就是父子节点上的房屋不能都偷窃，否则会报警。
用递归解决。递归函数的返回值有两个，第一个值是如果偷当前节点上的房子所获取的最高金额，第二个值是如果不偷当前节点上的房子所获取的最高金额。
主体伪代码应该是这样的：
left = func(root.left)
right = func(root.right)
steal = root.val + left[1] + right[1]
not_steal = max(left) + max(right)
或者这么写：not_steal = max(left[0], left[1]) + max(right[0], right[1])
return steal, not_steal
4带权爬楼梯
和爬楼梯问题类似，不过第i个阶梯对应着一个非负数的体力花费值cost[i]。每当爬上一个阶梯都要花费对应的体力花费值。爬的方式仍然是每次爬一个或者2个阶梯。问到达到楼层顶部的最低花费。在开始时，可以选择从索引为0或1的元素作为初始阶梯
定义dp[i]: 如果第i层阶梯就是楼层顶部，最低的花费。注意这种定义下：如果第i层阶梯是目标楼层时，最后的花费是不包含cost[i]的。假设最后从第k层阶梯爬上来，那么爬上第k层要花费对应的体力值cost[k]，然后从第k层直接1步或者2步来到楼层顶部(这里是第i层）。或者这么理解：楼层顶部不是阶梯，所以爬上楼层顶部没有体力花费。
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
要么爬上第i-1个阶梯，额外花费cost[i-1]，然后一步到达楼层。要么爬上第i-2个阶梯，额外花费cost[i-2]，然后2步来到楼层。
最后返回dp[n]
5网格中的路径数
从m x n 网格的左上角走到网格的右下角，每次只能向下或者向右移动一步，问总共有多少条不同的路径
定义dp[i][j]: 走到（i, j）时一共有多少条不同的路径数
dp[i][j] = dp[i-1][j] + dp[i][j-1]
走到（i, j）只有两种情况，要么从（i-1, j）向下移动一步，要么从（i, j-1）向右移动一步。
最后返回dp[m-1][n-1]
变种：格子里有个权值，求最大值: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
或者求最小路径和：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
6最大正方形
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
定义dp[i][j]: 以第（i, j）位置为右下角顶点的正方的最大边长（前提当然是矩阵（i，j）位置处为1）
if matrix[i][j]==1: dp[i][j] = min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1
else: dp[i][j]=0
大家可以自己画图看看，以（ij）为右下角的正方形，能不能在原来的基础上扩大边长，主要取决于左边、左上角、上边这3个相邻点的情况，且由最小的那个来决定。
在这个迭代的过程中，记录最大的边长，最后返回边长平方即可。
变种：还是0和1组成的二维矩阵，统计并返回其中完全由 1 组成的正方形子矩阵的个数。正方形子矩阵可能包括边长为1，边长为2，边长为i的正方形。那么可以定义dp[i][j]为以(i, j)为右下角的正方形的最大边长，同时也可以表示以(i, j)为右下角的正方形的数目。假设dp[i][j]=3，即以(i, j)为右下角的正方形的最大边长是3，那么以(i, j)为右下角的正方形共有3个，其边长分别为3，2，1。
7最长公共子序列
给定两个字符串 str1 和 str2，返回这两个字符串的最长公共子序列的长度（是子序列，不是连续子序列。比如“ab”是“acebad”的子序列）
定义dp[i][j]: str1[0...i]和str2[0...j]的最长公共子序列的长度。str1[0...i]表示str1中下标从0到i的这一段字符串。
如果str1[i] == str[j]，则dp[i][j] = dp[i-1][j-1] + 1
否则dp[i][j] = max(dp[i-1][j], dp[i][j-1])
当str1[i] 与 str[j]不相等时，dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])也是正确的。不过dp[i-1][j-1]一定小于等于dp[i-1][j]或者dp[i][j-1]（原因很好理解，无论dp[i-1][j]对应的字符串str2[0...j]，还是dp[i][j-1]对应的字符串str1[0...i]都比dp[i-1][j-1]对应的字符串多一个字符，那么有且只有两种可能，最长公共子序列长度加1，或者长度不变），所以可以省略以减少比较操作。
最后返回dp[i-1][j-1]
8最小编辑距离
给定两个字符串 str1 和 str2，计算将 str1 转换成 str2所使用的最少操作数。（可以使用3种操作：插入、删除、替换）
定义dp[i][j]: 将str1[0...i]转换成str2[0...j]所使用的最少操作数。str1[0...i]表示str1中下标从0到i的这一段字符串。
如果str1[i] == str[j]，则dp[i][j] = dp[i-1][j-1]
否则dp[i][j] = dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
简单解释：
如果str1[i] == str[j]，无需操作。
否则：
1）把str1[i]替换成str2[j]，需要的操作数是dp[i-1][j-1]+1
2）删除字符str1[i]后，str1[0...i-1]等于str2[j]，需要的操作数是dp[i-1][j]+1
3）在str1[0...i]后面插入字符str2[j]后，str1[0...i]+str2[j]等于str2[0...j]，需要的操作数是dp[i][j-1]+1
最后返回dp[n1][n2]（n1是str1的长度，n2是str2的长度）
9最长递增子序列
给定一个无序的整数数组nums，找到其中最长上升子序列的长度
定义dp[i]: 以nums[i]结尾的最长递增子序列的长度
dp[i] = Math.max(dp[i], dp[j] + 1) ,0<=j<i and nums[j] < nums[i]
遍历前面所有结尾比nums[i]小的子序列长度（把nums[i]加到最后，就形成了一个新的递增子序列，长度在原来的基础上加1），找最大的那个
最后返回max(dp)
10最长回文子序列
给定一个字符串s，找到其中最长的回文子序列。
定义dp[i][j]: 在子串 s[i..j] 中，最长回文子序列的长度
if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
else: dp[i][j] = max(dp[i+1][j], dp[i][j-1])
如果s[i] 等于s[j]，那么把s[i]，s[j]分别加在s[i+1..j-1]两侧，形成新的更长的回文子序列，长度为原来长度加2
如果s[i] 不等于s[j]，那么把s[i]，s[j]分别加在s[i+1..j-1]两侧，一定无法形成新的且长度比原来长2的回文子序列。但是把s[j]加在s[i+1...j-1]右侧，或者如果把s[i]加在s[i+1...j-1]左侧，则有可能形成新的更长的回文子序列。
最后结果返回dp[0][n-1]
11做菜顺序
一个厨师收集了他 n 道菜的满意程度 satisfaction ，这个厨师做出每道菜的时间都是 1 单位时间
一道菜的「喜爱时间」定义为烹饪这道菜以及之前每道菜所花费的时间乘以这道菜的满意程度，也就是 time[i]*satisfaction[i]
返回做完所有菜「喜爱时间」总和的最大值。可以按 任意 顺序安排做菜的顺序，也可以选择放弃做某些菜来获得更大的总和
定义dp[i][j]：前i个菜中选择做j个菜的最大喜爱时间
if satisfaction[i] == satisfaction[j]: dp[i][j] = dp[i-1][j-1] + j*satisfaction[i-1]
else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+j*satisfaction[i-1])
说明：首先需要对satisfaction 按从小到大排好序（相关证明略）。下标0表示第一个菜，下标i-1表示第i个菜。
如果第i个菜放弃，则dp[i-1][j]。
如果选择做第i个菜，那么这道菜的喜爱时间为j*satisfaction[i-1]。[j表示前面已做了j-1道菜，加上这道菜，花费了j单位时间]。加上之前的喜爱时间，就是dp[i-1][j-1]+j*satisfaction[i-1]。两者取最大值。
最后结果返回max(dp[len(satisfaction)])
这个问题用贪心效率更高。
12除数博弈
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
定义dp[i]： 黑板上数字是i的时候，爱丽丝的输赢情况（True表示爱丽丝可以取得胜利，False表示爱丽丝无法取得胜利）
dp[i] = True 如果存在一个x 且 dp[x]为False 且 i % x == 0 且 0<x<i
13三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的意思是下方或者右下方。
定义dp[i][j]： 走到（i,j）上的最小路径和
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
14最低票价
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
火车票有三种不同的销售方式：
一张为期一天的通行证售价为 costs[0] 美元；
一张为期七天的通行证售价为 costs[1] 美元；
一张为期三十天的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。返回想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。
定义dp[i]：完成第i天时的最低消费
如果第i天是旅行的日子：dp[i] = min(dp[max(i-1,0)]+costs[0], dp[max(i-7,0)]+costs[1], dp[max(i-30,0)]+costs[2])
否则: dp[i] = dp[i-1]
第i天有4种状态：a是不旅行的日子，消费保持不变；b花费一天的通行证，用以第i天的旅行；c利用前面某一天购买的7天通行证，第i天没有花费；d利用前面某一天购买的30天通行证，第i天没有花费。如果第i天是旅行的日子，那么最低消费一定是bcd中的最小值。
为什么？我们可以倒着想：假如x是最后一天旅行的日子，其花费的最小值取决于3个值，a第x-1天的花费+cost[0]（第x天买1天的通行证，第x天一定不需要买7天或者30天的通行证），b第x-7天的花费+cost1,c第x-30天的花费+cost[2]（第x-30+1天，也就是第x-29天，要买一张30天的通行证，从而第x天是这种通行证有效期内的最后一天）。我们看第x-30天的花费：如果在第x-29天买一张30天的通行证，那么可以覆盖第x-30天以后的所有30天，且最后一天是第x天。也就是说如果第x天使用的是30天的通行证，那么第x-29天买是最划算的。比如在第x-10天买，那么第x天的花费就是costs[2]+第x-11天的花费。而x-11>x-30，第x-11天的花费也一定大于等于x-30的花费（旅行的天数越多，花费也越多，当然也可能不变）。同理可以分析x-7和x-1。从而得出第x天的花费只依赖第x-1天、第x-7天、第x-30天的花费，子问题找到，也就是状态转移的过程。