动态规划专题总结
动态规划专题
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]
