动态规划 - DP - 《算法题》

子串问题

152. 乘积最大子数组

思路
- 根据正负性进行分类讨论。
- 状态: max代表以i结尾的连续子数组的最大乘积，min代表以i结尾的连续子数组的最小乘积
- 转移函数：
  - max = max(nums[i], maxnums[i], minnums[i])
  - min = min(nums[i], maxnums[i], minnums[i])
- 初始化: max = min = nums[0]
- 答案：一个变量ret，每次算完转移函数更新一下 ret = max(ret, max);
  238. 除自身以外数组的乘积
  5. 最长回文子串
516的简单版本

子序列问题

53. 最大子序和
思路
- 状态：以i结尾的每个数组的最大值
- 转移函数：
  300. 最长递增子序列
思路
- 贪心：子序列增长的越慢就越长
- 递增：d[i], 表示长度为i+1的子序列的最后一位的最小值，这是单调非递减的。
- 二分：
  - 如果大于数组最后一位，数组长度+1，将该数放入数组
  - 二分搜索出最右边的比该数小的数字，然后d[i+1] = 该数字。这里只能替换，不能插入，因为我们要找的是子序列，如果插入则不是合法的子序列了。例如，[1, 5, 3] - > [1, 5] 插入3，就会变成[1, 3, 5]，但他不是子序列，因为移动了元素的相对位置。
    392. 判断子序列
双指针，秒杀了。

1143.最长公共子序列
思路
- 状态: dp[i][j] 表示str1[:i]和str[:j]之间的最长公共子序列
- 转移函数：
  - str[i] == str[j] -> dp[i][j] = 1 + dp[i-1][j-1]
  - str[i] != str[j] -> dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
- 初始化: dp[0][i] = 0 and dp[j][0] = 0, 第一行，第一列都是0
- 答案dp[m][n]
  72. 编辑距离
思路
- 状态: dp[i][j] 表示str1[:i]和str[:j]之间的最短编辑距离
- 转移函数：
  - str[i] == str[j] -> up_left = dp[i-1][j-1]
  - str[i] != str[j] -> up_left = dp[i-1][j-1]+1
  - dp[i][j] = min(up_left, dp[i-1][j] + 1, dp[i][j-1] + 1)
- 初始化: dp[0][i] = i and dp[j][0] = j, 第一行，第一列都是和行/列序号一致的值
- 答案dp[m][n]
  面试题 01.05. 一次编辑
同Q72

剑指 Offer II 119. 最长连续序列
这个不是规范的子序列，元素的相对位置可以互换的。

516. 最长回文子序列
思路
- 状态：dp[i][j]表示子串i到j之间的最长回文子序列
- 转移函数：
  - s.charAt(i) == s.charAt(j)
    - if j - i < 3 -> dp[i][j] = j - i + 1
    - else -> dp[i][j] = 2 + dp[i+1][j-1]
  - s.charAt(i) != s.charAt(j)
    - dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
- 初始化: dp[i][i] = 1
- 答案：dp[0][n-1]
  斐波那契数列
  509. 斐波那契数
简单，秒杀
O(logn)的最优解
- 矩阵快速幂
  70. 爬楼梯
思路：保存前1步和2步的答案，然后迭代到n为止。

746. 使用最小花费爬楼梯
思路：一个一维DP数组

股票问题

121. 买卖股票的最佳时机
简单，秒杀。
思路：保存买入价，如果遇到更低的价格更新买入价，如果遇到更高的价格，更新最大利润。正向遍历完数组就可以求的最大利润。

122. 买卖股票的最佳时机 II
思路1：典型的贪心问题。
思路2: 动态规划
- 状态: dp[i][0]：第i天手里没有股票的最大利润 dp[i][1]: 第i天手里有股票的最大利润
- 转移函数：
  - dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
  - dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1]][1])
    123. 买卖股票的最佳时机 III （HARD）
    188. 买卖股票的最佳时机 IV （HARD）
    309. 最佳买卖股票时机含冷冻期
思路2: 动态规划
- 添加一个冷冻期的状态
- 状态: dp[i][0]：第i天手里没有股票的最大利润 dp[i][1]: 第i天手里有股票的最大利润 dp[i][2]: 第i天处于冷冻期的最大利润，此处意味着下一天无法购买。
- 转移函数：
  - dp[i][0] = max(dp[i-1][0], dp[i-1][2])
  - dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1]][1])
  - dp[i][1] = dp[i-1][1] + price[i]
- 初始化: dp[0][0] = 0, dp[0][1] = -prices[0], dp[0][2] = 0;
- 答案 max(dp[n-1][0], dp[n-1][2])
  714. 买卖股票的最佳时机含手续费
思路1：典型的贪心问题。
- 初始化: buy = prices[0] + fee
- if (prices[i] > buy)
  - ret += prices[i] - buy
  - buy = prices[i] // 免除手续费买入，遇到更高价，直接赚取差价，因为手续费在这次交易已经交过了
- if (prices[i] + fee < buy)
  - buy = prices[i] + fee
思路2: 动态规划
- 状态: dp[i][0]：第i天手里没有股票的最大利润 dp[i][1]: 第i天手里有股票的最大利润
- 转移函数：
  - dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)
  - dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1]][i])
    打家劫舍
    198. 打家劫舍
状态: dp[i]：在前i间屋子最多可得到的钱
转移函数：
- dp[i] = max(dp[i-1], dp[i-2] + nums[i])
初始化: dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]);
答案 dp[n-1]

213. 打家劫舍 II
198 -> 变成环转数组，首尾相连。
思路：【分类讨论】其实就是把环拆成两个队列，一个是从0到n-1，另一个是从1到n，然后返回两个结果最大的。

337. 打家劫舍 III
198 -> 变成二叉树结构 -> 树形DP

石子游戏

877. 石子游戏

状态: dp[i][j]：在区间i到j之间，先手玩家可以造成和对手石子数差距的最大值
转移函数：
- dp[i][j] = max(stones[i]+dp[i+1][j], stones[j]+dp[i][j-1])
初始化: dp[i][i] = stones[i]
答案 dp[0][length-1] > 0
注意：从下往上开始fill dp matrix

1140. 石子游戏 II(频率0.69%)
dp[i][j]表示剩余[i : len - 1]堆时，M = j的情况下，先取的人能获得的最多石子数
- i + 2M >= len, dp[i][M] = sum[i : len - 1], 剩下的堆数能够直接全部取走，那么最优的情况就是剩下的石子总和
- i + 2M < len, dp[i][M] = max(dp[i][M], sum[i : len - 1] - dp[i + x][max(M, x)]), 其中 1 <= x <= 2M，剩下的堆数不能全部取走，那么最优情况就是让下一个人取的更少。对于我所有的x取值，下一个人从x开始取起，M变为max(M, x)，所以下一个人能取dp[i + x][max(M, x)]，我最多能取sum[i : len - 1] - dp[i + x][max(M, x)]。

DP

子串问题

子序列问题

斐波那契数列

股票问题

123. 买卖股票的最佳时机 III （HARD）

188. 买卖股票的最佳时机 IV （HARD）

打家劫舍

石子游戏

1140. 石子游戏 II(频率0.69%)

字符串匹配

鸡蛋或者其他物品掉落

887. 鸡蛋掉落（hard）

会议室

状态压缩DP

数位DP

剪绳子