动态规划

解题思路

问题需要满足原则：最优子结构

使用过程中需要确定：

（0）目标

求背包中最大价值

（1）状态

比如0-1背包问题，状态是“背包容量”和“可选择的物品”。

// 状态
for (int i = 1; i < GOODS_NUM; i ++) {
    for (int j = 1; j < BAG_CAP; j ++) {
        // 做选择
    }
}

（2）选择

// 状态
for (int i = 1; i < GOODS_NUM; i ++) {
    for (int j = 1; j < BAG_CAP; j ++) {
        // 做选择
        dp[i][j] = max 价值 (物品i放进背包, 物品i不放进背包)
    }
}

典型问题

子序列问题

模板

int	n = arr.length;
int[][] dp = new dp[n][n];
for	(int i = 0; i < n; i++) {
    for	(int j = 0; j < n; j++) {
    if	(arr[i] == arr[j])	
        dp[i][j] = dp[i][j]	+ ...
    else
        dp[i][j] = 最值(...)
    }
}

（1）涉及到两个字符串

LeetCode 1143 最长公共子序列（LCS, Longest Common Subsequence）

dp[i][j]的含义是:对于s1[1..i]和s2[1..j],它们的LCS⻓度是dp[i][j]

（2）涉及一个字符串

LeetCode 516 最⻓回文子序列（LSI）

备忘录（数组）形式的动态规划

0-1背包问题

完全背包问题

子集背包问题

最长公共子序列

最长公共子序列就是一个典型的“dp的状态转移矩阵只依赖于之前的结果”的情况。所以可以使用递归+动态规划方式，也可以使用数组的方式。

递归 + 动态规划

扔鸡蛋问题

使用递归的方式实现动态规划

不能使用数组的原因：不能使用数组形式实现的原因是某一个dp需要依赖的其他dp可能还没有计算出来。比如，

dp[i][j] = max(dp[i - 1][N - j], dp[i][j - 1])

我们这里可能无法知道dp[i - 1][N - j]或者dp[i][j - 1]，所以也就无法得到这个结果了。如果采用递归/回溯的方式，则可以得到任意的dp。然后将该DP结果保存到hash map中就可以起到备忘录的效果。

怎么样的情况才能使用数组形式的dp呢？应该是

dp的状态转移矩阵只依赖于之前的结果（见最长公共子序列），比如

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])