# 动态规划：更高效的穷举！
# 动态规划的基本原理
动态规划并不是一种具体的算法，而是一种思想，个人觉得就是缓存+枚举，把求解的问题分成许多阶段或者多个子问题，然后按顺序求解各子问题。前一子问题的解为后一子问题提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
所以动态规划一般用来求最优解（对子问题进行决策），求种类数（对子问题进行加和）
先分享几个经典的动态规划实现，后续再分析几个面试题
# 数塔问题
题目描述：
题目来源：LeetCode 120. 三角形最小路径和
思路：把这个图形换一下，方便讲递推公式
[2],
[3,4],
[6,5,7],
[4,1,8,3]
我们可以从底到顶来算最优值。
dp[i][j]为从最底部到第i行第j列的最小路径和，value[i][j]为第i行第j列的值，状态转移方程为
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}
// 这里行和列加1，是为了不用处理最下面一行的边界
int[][] dp = new int[triangle.size() + 1][triangle.size() + 1];
for (int i = triangle.size() - 1; i >= 0; i--) {
List<Integer> rows = triangle.get(i);
for (int j = 0; j < rows.size(); j++) {
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + rows.get(j);
}
}
return dp[0][0];
}
}
# 线性动态规划
线性动态规划，就是该问题的模型是线性的，数据结构表现为线性表的形式
# 最长上升子序列
来源：LeetCode 300.最长上升子序列 描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
思路：子序列有很多，最长的长度为4
我们假设dp[i]存的是到第i个元素时，数组的最长子序列，则对应的状态转移方程为
dp[i] = max{1, dp[j] + 1 | j < i 且 arr[j] < arr[i]}
其中1为只有自己一个元素，则递增子序列的长度为1
public class Solution {
public int lengthOfLIS(int[] nums) {
int max = 0;
int[] dp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j] && (dp[j] + 1) > dp[i]) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > max) {
max = dp[i];
}
}
return max;
}
}
# 最长公共子序列
题目描述：
题目来源：LeetCode 1143
思路：这个题确实比较抽象，上图
s1=a s2=a，最长公共子串长度为1
s1=ac s2=abc，对应的公共子串长度为2
dp[i][j]为第一个字符串长度为i和第二个字符串长度为j时对应的最长公共子串 状态转移方程为
if(s1.charAt(i) == s2.charAr(j))
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = Math.max(dp[i-1][j], dp[i][j -1]);
还是画图演示一下递推公式
public class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
for (int i = 0; i < text1.length(); i++) {
for (int j = 0; j < text2.length(); j++) {
if (text1.charAt(i) == text2.charAt(j)) {
dp[i + 1][j + 1] = dp[i][j] + 1;
} else {
dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
}
}
}
return dp[text1.length()][text2.length()];
}
}
# 最长公共子串
题目描述：
题目来源：BM66（牛客网）
public class Solution {
public String LCS (String str1, String str2) {
int max = 0;
int lastIndex = 0;
int[][] dp = new int[str1.length() + 1][str2.length() + 1];
for (int i = 0; i < str1.length(); i++) {
for (int j = 0; j < str2.length(); j++) {
if (str1.charAt(i) == str2.charAt(j)) {
dp[i + 1][j + 1] = dp[i][j] + 1;
if (dp[i + 1][j + 1] > max) {
max = dp[i + 1][j + 1];
lastIndex = i;
}
}
}
}
return str1.substring(lastIndex - max + 1, lastIndex + 1);
}
}
# 背包性动态规划
背包问题：每个物品有其特有的价值和体积，装取的体积总和不超过体积上限的一些物品，最大化装取物品价值总和的问题
是男人就看《背包九讲》，作为动态规划的入门课，《背包九讲》必不可少。这次就只分享背包九讲中最简单的01背包
来源：蓝桥杯 问题描述：给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个. 输入格式 输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。 以后N行每行两个数Wi和Vi,表示物品的重量和价值 输出格式 输出1行，包含一个整数，表示最大价值。 样例输入 3 5 2 3 3 5 4 7 样例输出 8 数据规模和约定 1<=N<=200,M<=5000.
思路：这是最简单的01背包，都不带变形的，每种物品仅有一件，可以选择放或不放。
第i件物品的重量是w[i]，价值是v[i] 用dp[i][j]表示前i件物品放入一个承重为j的背包可以获得的最大价值，状态转移方程为
dp[i][j] = max{dp[i-1][j], dp[i-1][j-w[i]] + c[i]}
即
dp[i][j] = max{不放第i件物品，放第i件物品}
你可以照着这个状态转移方程自己写一下，我下面这种写法直接用了滚动数组，把数组从二维变成了一维，节省了空间，有兴趣的可以参考其他博客学习这种写法，本文就不深入了。
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] widght = new int[210];
int[] value = new int[210];
int[] dp = new int[5010];
for (int i = 0; i < n; ++i) {
widght[i] = in.nextInt();
value[i] = in.nextInt();
}
for (int i = 0; i < n; ++i) {
for (int j = m; j >= widght[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - widght[i]] + value[i]);
}
}
System.out.println(dp[m]);
}
}
# 分割等和子集
来源：LeetCode 416. 分割等和子集 描述：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
思路：很典型的01背包，背包的容量为元素和的一半，最后看背包是否能填满即可 之前已经说了01背包的状态转移方程
第i件物品的重量是w[i]，价值是v[i] 用dp[i][j]表示前i件物品放入一个承重为j的背包可以获得的最大价值，状态转移方程为
dp[i][j] = max{dp[i-1][j], dp[i-1][j-w[i]] + c[i]}
即
dp[i][j] = max{不放第i件物品，放第i件物品}
在这个题目中，承重和价值都是这个值的大小，因为上一次例子用到了压缩数组的写法，这次就换一种写法，完全按照状态转移方程来
public class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
// 奇数直接false
if ((sum & 1) == 1) {
return false;
}
int target = sum >> 1;
int[][] dp = new int[nums.length][target + 1];
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j <= target; j++) {
if (j >= nums[i]) {
if (i == 0) {
dp[i][j] = nums[i];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
}
}
}
}
return dp[nums.length - 1][target] == target;
}
}
最后留个思考题，分割等和子集这个题的状态转移方程除了我写的这个，你还能写出其他的吗？
# 区间类型动态规划
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + calc())
区间 dp 的阶段划分是区间长度，我们需要保证长度较短的区间全部处理完之后，再处理长度比较长的区间，所以最外层循环就需要枚举区间长度，然后就是枚举区间的左右端点了
# 矩阵类型动态规划
# 减绳子
来源：《剑指offer》第二版
描述：给你一根长度为n的绳子，请把绳子剪成m段 (m和n都是整数，n>1并且m>1)每段绳子的长度记为k[0],k[1],…,k[m].请问k[0]k[1]…*k[m]可能的最大乘积是多少？例如，当绳子的长度为8时，我们把它剪成长度分别为2,3,3的三段，此时得到的最大乘积是18.
思路：定义函数f(n)为长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀的时候，我们有n-1种可能的选择，也就是剪出来的第一段绳子的长度分别为1,2...n-1。因此f(n)=max(f(i)*f(n-i))，其中0<i<n。这是一个从上至下的递归公式，递归会有很多重复的子问题。我们可以从下而上的顺序计算，也就是说我们先得到f(2)，f(3)，再得到f(4)，f(5)，直到得到f(n)
假设dp[i]表示长度为i的绳子能得到的最大乘积，则状态转移方程为
dp[i] = max(dp[i], dp[j] * dp[i-j])
public class Solution {
public int maxNumAfterCutting(int n) {
if (n < 2)
return 0;
// 绳子长度为2时，只能剪成1和1
if (n == 2)
return 1;
// 只可能为长度为1和2的2段或者长度都为1的三段，最大值为2
if (n == 3)
return 2;
// 当长度大于3时，长度为3的段的最大值是3
int product[] = new int[n+1];
product[0] = 0;
product[1] = 1;
product[2] = 2;
product[3] = 3;
int max = 0;
for (int i = 4; i <= n; i++) {
max = 0;
for (int j = 1; j <= i / 2; j++) {
int sum = product[j] * product[i - j];
if (sum > max) {
max = sum;
product[i] = max;
}
}
}
return product[n];
}
}
代码中第一个for循环变量i是顺序递增的，这意味着计算顺序是自下而上的。因此再求f(i)之前，对于每一个j(0<i<j)而言，f(j)都已经求解出来了，并且保存在product[j]里。为了求解f(i)，我们需要求出所有可能的f(i)*f(i-j)并比较得出他们的最大值，这就是代码中第二个for循环的功能
这个面试题又比第一个面试题难了一点，因为第一个面试题仅仅是将一个大问题划分成几个子问题，并没有根据局部解进行决策得到最优解，而这个面试题体现了决策的过程
# 接雨水
来源：LeetCode 42. 接雨水 描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）
示例： 输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6
思路：思路还是比较简单，对每一个柱子能存多少水求和即可，这样只需要获取这个柱子左边的最高高度和这个柱子右边的最高高度，2者的最小值减去柱子的高度就是这个柱子的存水量
class Solution {
public int trap(int[] height) {
int sum = 0;
for (int i = 0; i < height.length; i++) {
int maxLeft = 0, maxRight = 0;
// 对i这个柱子，左边柱子的最高值
for (int left = 0; left < i; left++) {
maxLeft = Math.max(maxLeft, height[left]);
}
// 对i这个柱子，右边柱子的最高值
for (int right = i + 1; right < height.length ; right++) {
maxRight = Math.max(maxRight, height[right]);
}
// i这个柱子能存的水量
int temp = Math.min(maxLeft, maxRight) - height[i];
if (temp > 0)
sum += temp;
}
return sum;
}
}
每次都要算某个柱子的左右最值，时间复杂度是O(n2)，能不能把算左右最值的效率提高呢？这就用到动态规划了，假如说
我们用dp[i]，表示到第i个柱子（包括第i个柱子）左边的最大值，height[i]为第i个柱子的高度，右边同理，则状态转移方程为
dp[i] = max(dp[i-1], height[i])
class Solution {
public int trap(int[] height) {
int sum = 0;
int len = height.length;
if (len == 0)
return 0;
int[] maxLeft = new int[len];
int[] maxRight = new int[len];
maxLeft[0] = height[0];
for (int i = 1; i < len; i++) {
maxLeft[i] = Math.max(height[i], maxLeft[i-1]);
}
maxRight[len - 1] = height[len - 1];
for (int i = len - 2; i >= 0; i--) {
maxRight[i] = Math.max(height[i] ,maxRight[i+1]);
}
for (int i = 0; i < height.length; i++) {
sum += Math.min(maxLeft[i], maxRight[i]) - height[i];
}
return sum;
}
}
这样时间复杂度就变成O(n)了
# 树形动态规划
来源：https://leetcode.cn/problems/house-robber-iii/description/
超时代码
class Solution {
public int rob(TreeNode root) {
return Math.max(dp(root, true), dp(root, false));
}
public int dp(TreeNode root, boolean canTake) {
if (root == null) {
return 0;
}
if (canTake) {
int num1 = dp(root.left, true) + dp(root.right, true);
int num2 = root.val + dp(root.left, false) + dp(root.right, false);
return Math.max(num1, num2);
} else {
return dp(root.left, true) + dp(root.right, true);
}
}
}