一些典型的动态规划问题

斐波那契数列

0 1 1 2 3 5…【f(0) = 0, f(1) = 1】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 基本的递归解法:
* 比如计算 fib(5),递归树如下,我们发现有很多重复的计算!
* 递归方程:f(n) = f(n-1) + f(n-2), f(1)=1,f(0)=0
*
* f5
* f4 f3
* f3 f2 f2 f1
* f2 f1 f1 f0 f1 f0
* f1 f0
*
* 时间复杂度 O(2ⁿ)
* 空间复杂度 O(n)
*/
private static int fib(int n) {
if (n == 0 || n == 1) return n;
return fib(n-1) + fib(n-2);
}

使用记忆化搜索进行优化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 记忆化搜索的优化思路:
* 自然地,能想到的优化的方法是,暂时存放元素机计算过的 fib(i),这时候递归树变成了:
*
* f5
* f4
* f3
* f2
* f1 f0
*
* 时间复杂度:O(n)
* 空间复杂度:O(n)
*/
private static int fib(int n, int[] memo) {
if (n == 0 || n == 1) return n;

if (memo[n] != 0) return memo[n];
memo[n] = fib(n-1, memo) + fib(n-2, memo);

return memo[n];
}

延伸到动态规划问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 动态规划思路:动态规划本质就是加了一个递归备忘录
* 动态规划状态转移方程:dp[i] = dp[i-1] + dp[i-2]
*/
private static int fib(int n) {
if (n == 0 || n == 1) return n;

// dp table
int[] dp = new int[n+1];
// base case
dp[0] = 0;
dp[1] = 1;
// 状态转移
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}

对上面动态规划的简化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 通过观察我们发现,只需要维护 dpn_1 和 dpn_2 两个状态即可,不必存储全部的 dp 表
*
* 时间复杂度:O(n)
* 空间复杂度:O(1)
*/
public static int fib(int n) {
if (n == 0 || n == 1) return n;

int dp1 = 1, dp2 = 0;
int cur = 0;
for (int i = 2; i <= n; i++) {
cur = dp1 + dp2;
dp2 = dp1;
dp1 = cur;
}
return cur;
}

斐波那契数列问题的变种 - 爬楼梯问题:每次爬一个或者两个台阶,爬n个台阶共有多少种爬法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 你站在楼梯底下,每次可以迈 1 阶 或 2 阶。
* 核心直觉是,到达第 n 阶,只有两种可能:
* 从第 n-1 阶迈 1 步上来
* 从第 n-2 阶迈 2 步上来
* 所以,到第 n 阶的方法数 = 到第 n-1 阶的方法数 + 到第 n-2 阶的方法数,这就是斐波那契数列。
*/
public static int countClimbTheStairs(int n) {
if (n <= 2) return n;

int prevII = 1; // n=1 时的爬法
int prevI = 2; // n=2 时的爬法

for (int i = 3; i <= n; i++) {
int cur = prevI + prevII; // 当前 = 前一步 + 前两步
prevII = prevI;
prevI = cur;
}
return prevI;
}


卡丹算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* 给定整数数组 nums(含负数),找连续子数(至少含 1 个元素),使其元素和最大,返回该最大和。
* 示例:[-2,1,-3,4,-1,2,1,-5,4] → 最大和为 6(对应子数组 [4,-1,2,1])
*
* 以当前元素结尾的最大子数组和:dp[i] = max(dp[i-1] + a[i], a[i])
* 而最大的全局子数组和还需要和前一个最大子数组和进行比较
* 即 dp[0] = a[0], globalMax = max(dp[i], globalMax)
*/
public class KadaneTest {

public static void main(String[] args) {
int[] array = {-2,1,-3,4,-1,2,1,-5,4};
System.out.println(maxSubArray(array)); // 输出 6,对应的最大子数组 [4,-1,2,1]
}

public static int maxSubArray(int[] nums) {
int dp = nums[0]; // dp[i-1]:以 i-1 结尾的最大子数组和
int globalMax = nums[0]; // 全局最大

for (int i = 1; i < nums.length; i++) {
dp = Math.max(dp + nums[i], nums[i]); // dp[i]
globalMax = Math.max(globalMax, dp);
}
return globalMax;
}
}


最长公共子序列

不连续的情况

最长公共子序列(LCS,Longest Common Subsequence):给定两个字符串(或序列)text1 和 text2,找出它们的最长公共子序列的长度。注意是子序列,不要求连续,但要求相对顺序一致。例如:

1
2
3
4
5
6
7
8
9
text1 = "abcde"
text2 = "ace"
↑ ↑ ↑
LCS = "ace",长度 = 3


text1 = "abc"
text2 = "def"
LCS = "",长度 = 0

这是一个典型的二维 DP 问题,因为状态同时依赖两个序列的位置——需要一张二维表来记录 “看到 text1 的前 i 个字符、text2 的前 j 个字符时,LCS 有多长”。

状态定义

这里 i、j 从 1 开始,对应字符串下标 i-1、j-1

1
dp[i][j] = text1 的前 i 个字符 与 text2 的前 j 个字符 的 LCS 长度

状态转移方程

1
2
3
4
5
6
7
# 字符相等 → 两个都往前退一格,LCS 长度 +1
字符相等:text1[i-1] == text2[j-1]
转移方程:dp[i][j] = dp[i-1][j-1] + 1

# 字符不等 → 要么退 text1 的一个字符,要么退 text2 的一个字符,取两者中较大的
字符不等:text1[i-1] != text2[j-1]
转移方程:dp[i][j] = max(dp[i-1][j], dp[i][j-1])

用示例走一遍:(text1 = “abcde”,text2 = “ace”),右下角 dp[5][3] = 3

∅ a c e
∅ 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void main(String[] args) {
String text1 = "abcde";
String text2 = "ace";
int result = lcs(text1, text2);
System.out.println(result); // 3
}

public static int lcs(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}

如果要输出具体的 LCS 字符串:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* 当前位置 (i, j):
* 如果 text1[i-1] == text2[j-1] → 字符属于 LCS,i--, j--
* 否则如果 dp[i-1][j] > dp[i][j-1] → i--
* 否则 → j--
* 直到 i==0 或 j==0 停止
*/
public static String lcsString(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];

// 填表
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (text1.charAt(i - 1) == text2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

// 回溯
StringBuilder sb = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
sb.append(text1.charAt(i - 1));
i--; j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return sb.reverse().toString();
}


连续的情况

子串和子序列的唯一区别就是:子串要求连续。这个”连续”的约束,直接让 DP 的转移方程变简单了。

状态转移方程:

1
2
text1[i-1] == text2[j-1]  →  dp[i][j] = dp[i-1][j-1] + 1
text1[i-1] != text2[j-1] → dp[i][j] = 0 ← 断了!归零!

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int lcs2(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
int maxLen = 0;

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxLen = Math.max(maxLen, dp[i][j]);
}
// 不等时 dp[i][j] 默认为 0,不用写
}
}
return maxLen;
}

如果要输出具体子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static String lcsString2(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
int maxLen = 0;
int endIndex = 0; // text1 中公共子串的结束位置

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
endIndex = i - 1;
}
}
}
}
return text1.substring(endIndex - maxLen + 1, endIndex + 1);
}


零钱兑换问题

给定不同面额的硬币 coins 和一个总金额 amount,计算凑成总金额所需的最少硬币个数。如果无法凑成,返回 -1。每种硬币可以无限次使用(完全背包)。比如:

1
2
3
4
5
coins = [1, 2, 5], amount = 11
→ 最少需要 3 枚硬币:11 = 5 + 5 + 1

coins = [2], amount = 3
→ 无法凑成,返回 -1

为什么用 DP?这是因为 “凑 amount 最少需要几枚硬币”——这个最优解可以拆成子问题:凑 amount 的最优解 = 选一枚硬币 coin,然后凑 amount - coin 的最优解 + 1,而凑 amount - coin 的最优解,和凑 amount 的结构完全一样——这是典型的最优子结构 + 重叠子问题。

状态定义

1
dp[i] = 凑成金额 i 所需的最少硬币数

状态转移方程

1
2
# 含义:凑金额 i,我选一枚 coin,剩下的 i - coin 用之前算好的最优方案凑。
dp[i] = min( dp[i - coin] + 1 ) 对所有 coin <= i

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];

// 初始化为 amount+1(比理论最大值还大,表示"不可达")
Arrays.fill(dp, amount + 1);
dp[0] = 0;

// 从 1 元开始,一步步算到目标金额,每一步都尝试用所有硬币,选最省的方案
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i >= coin) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}

return dp[amount] > amount ? -1 : dp[amount];
}


背包问题

背包问题是动态规划里最大、最系统的一个家族。什么是背包问题呢?就是给你一堆物品,每个物品有重量和价值。给你一个容量有限的背包。问:怎么选物品,使得总重量不超过背包容量,且总价值最大?不同变体区别就在于:每个物品能选几次。


0/1 背包

问题描述:

  • n 个物品,每个物品只能选一次(选或不选)
  • 重量数组 weight[],价值数组 value[]
  • 背包容量 W
  • 求最大价值

具体示例:

1
2
3
4
weight = [1, 3, 4]
value = [15, 20, 30]
W = 4
→ 选物品0(重1,值15) + 物品1(重3,值20) = 重4, 值35

状态定义:

1
dp[i][j] = 考虑前 i 个物品,背包容量为 j 时,能获得的最大价值

状态转移方程:

1
2
3
4
# 对第 i 个物品(重量 weight[i-1]、价值 value[i-1]),两种选择:
# 不选 dp[i-1][j]
# 选(要求 j >= weight[i-1]) dp[i-1][j-weight[i-1]] + value[i-1]
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1])

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int knapsack01(int[] weight, int[] value, int W) {
int n = weight.length;
int[][] dp = new int[n + 1][W + 1];

for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
if (j >= weight[i - 1]) {
dp[i][j] = Math.max(
dp[i - 1][j],
dp[i - 1][j - weight[i - 1]] + value[i - 1]
);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][W];
}

空间优化:滚动数组 O(W)。dp[i] 只依赖 dp[i-1],而且只用到了更小的容量(j 往小的方向看),所以可以用一维数组 + 从后往前遍历。为什么从后往前? 因为从前往后会覆盖 dp[j - weight[i]] 的值,导致同一个物品被选了多次(变成完全背包了)。

1
2
3
4
5
6
7
8
9
10
public static int knapsack01(int[] weight, int[] value, int W) {
int[] dp = new int[W + 1];

for (int i = 0; i < weight.length; i++) {
for (int j = W; j >= weight[i]; j--) { // ← 从后往前!
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[W];
}


完全背包

和 0/1 背包一样,但每个物品可以选无限次。

1
2
3
4
weight = [1, 3, 4]
value = [15, 20, 30]
W = 4
→ 选 4 个物品0 = 重4, 值60 (每个物品无限用)

转移方程

1
2
# 注意!选了之后还是 dp[i](不是 dp[i-1]),因为可以再选。
dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i-1]] + value[i-1])

代码实现(一维优化版)

1
2
3
4
5
6
7
8
9
10
public static int unboundedKnapsack(int[] weight, int[] value, int W) {
int[] dp = new int[W + 1];

for (int i = 0; i < weight.length; i++) {
for (int j = weight[i]; j <= W; j++) { // ← 从前往后!
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[W];
}


多重背包

和 0/1 背包一样,但每个物品不是只能选 1 次,也不是无限次,而是有数量上限 count[i]。问怎么选总价值最大?

1
2
3
物品0:重量 2,价值 3,数量 2 件
物品1:重量 3,价值 4,数量 3 件
背包容量 W = 10

最直觉的解法:直接拆成 0/1 背包,每个物品有几件,就当成几个独立物品丢进 0/1 背包:

1
2
物品0 有 2 件 → 当成 2 个"重量2、价值3"的独立物品
物品1 有 3 件 → 当成 3 个"重量3、价值4"的独立物品

总共 5 个物品,直接跑 0/1 背包。

1
2
3
4
5
6
7
8
// 暴力拆分
for (int i = 0; i < n; i++) {
for (int k = 0; k < count[i]; k++) {
for (int j = W; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
}

能跑通,但太慢了。时间复杂度:O(W × 所有物品数量之和)。如果某个物品有 10000 件,就傻了。怎么优化呢?可以使用二进制优化的思想,不需要把 13 件物品拆成 13 个独立的,只需要拆成 4 个”打包好的组”,就能组合出 0~13 件的任何选择。任何数字都可以用二进制位表示。比如 13:

1
13 = 8 + 4 + 1    ← 但 1+2+4+8 = 15 > 13,不行

正确拆法:1, 2, 4, 6

1
2
3
4
5
6
7
8
9
10
11
12
13
1 = 1
2 = 2
3 = 1+2
4 = 4
5 = 1+4
6 = 2+4
7 = 1+2+4
8 = 2+6
9 = 1+2+6
10 = 4+6
11 = 1+4+6
12 = 2+4+6
13 = 1+2+4+6

0~13 的任意数量都能用这几个”包”的组合凑出来!具体的拆法就是不断取 2 的幂,直到剩下的不够下一个幂:

1
2
3
4
5
6
count = 13
取 1 → 剩 12
取 2 → 剩 10
取 4 → 剩 6
取 8?不行(8 > 6),把剩下的 6 作为一个包
→ 拆成:1, 2, 4, 6

每个包的重量和价值乘以对应的倍数:

1
2
3
4
5
6
原物品:重量 w,价值 v,数量 13
拆成:
包1:重量 1*w,价值 1*v
包2:重量 2*w,价值 2*v
包3:重量 4*w,价值 4*v
包4:重量 6*w,价值 6*v

然后把这 4 个包当成 0/1 背包里的 4 个独立物品。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int multipleKnapsack(int[] weight, int[] value, int[] count, int W) {
int[] dp = new int[W + 1];

for (int i = 0; i < weight.length; i++) {
int w = weight[i], v = value[i], c = count[i];

// 二进制拆分
for (int k = 1; c > 0; k *= 2) {
int take = Math.min(k, c); // 这一包的大小
c -= take; // 剩余数量

int packW = take * w; // 这一包的重量
int packV = take * v; // 这一包的价值

// 当成 0/1 背包的一个物品
for (int j = W; j >= packW; j--) {
dp[j] = Math.max(dp[j], dp[j - packW] + packV);
}
}
}
return dp[W];
}


分组背包

如果说前面的背包问题是在“数量”上做文章(1个、无限个、有限个),那么分组背包则是改变了物品之间的互斥关系。有 N​ 组物品和一个容量为 W 的背包。第 ​i 组中包含若干个物品,这些物品相互之间是互斥的(即每组里面最多只能选择一个物品装入背包)。 每件物品有自己的重量 weight 和价值 value​。求在不超过背包容量的情况下,能装入的最大总价值。

状态定义,设 $dp[i][j]$ 表示:从前 $i$ 组物品中选择,在容量限制为 $j$ 的背包下所能获得的最大价值。

状态转移方程,当我们面对第 $i$ 组物品时,我们的决策分成两部分:

  • 不选第 $i$ 组的任何物品:价值继承自前 $i-1$ 组,即 $dp[i-1][j]$。
  • 选择第 $i$ 组中的某一个物品 $k$:既然选了第 $i$ 组的物品 $k$(其重量为 $w_k$,价值为 $v_k$),那么背包容量要扣除 $w_k$,且不能再选该组其他物品,其价值为 $dp[i-1][j - w_k] + v_k$。因此,状态转移方程为:$dp[i][j] = \max\left( dp[i-1][j], \ \max_{k \in \text{group } i} (dp[i-1][j - weight[k]] + value[k]) \right)$

和前面的背包类似,二维数组可以压缩为一维数组 $dp[j]$。但分组背包的循环嵌套顺序至关重要,稍微写错就会导致逻辑崩塌。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class GroupedKnapsack {

static class Item {
int weight;
int value;
public Item(int weight, int value) {
this.weight = weight;
this.value = value;
}
}

public static int groupKnapsack(int W, List<List<Item>> groups) {
int[] dp = new int[W + 1];

// 1. 遍历每一组
for (List<Item> group : groups) {
// 2. 倒序遍历背包容量
for (int j = W; j >= 0; j--) {
// 3. 遍历组内每个物品,看选哪个收益最高
for (Item item : group) {
if (j >= item.weight) {
dp[j] = Math.max(dp[j], dp[j - item.weight] + item.value);
}
}
}
}
return dp[W];
}
}


股票买卖模型

I 型:交易一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 买卖股票的最佳时机 (Best Time to Buy and Sell Stock)
* 题目描述:
* 给定股票价格数组,计算一次交易的最大利润。
* 示例:
* 输入:[7,1,5,3,6,4]
* 输出:5(1买6卖)
* 最优解思路:
* 遍历价格数组,维护历史最低价 min_price 和最大利润 max_profit。
* 时间复杂度:O(n)
* 空间复杂度:O(1)
*/
public int maxProfitI(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price; // 更新历史最低价
} else {
maxProfit = Math.max(maxProfit, price - minPrice); // 尝试卖出
}
}
return maxProfit;
}

II 型:多次交易

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 买卖股票 II
* 可以多次交易,贪心,只要涨就卖
*/
public int maxProfitII(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}

III 型:最多 k 次交易

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* 买卖股票
* 最多 k 次交易,求最大利润。这是股票系列的 "终极 DP 版"。
*
* 状态定义
* buy[j] = 完成 j 次交易(处于买入状态)的最大利润
* sell[j] = 完成 j 次交易(处于卖出状态)的最大利润
* 为什么需要"买入状态"和"卖出状态"分开?因为一次交易 = 一次买 + 一次卖,必须按顺序来。
*
* 状态转移方程
* buy[j] = max(buy[j], sell[j-1] - price) // 第 j 次买入
* sell[j] = max(sell[j], buy[j] + price) // 第 j 次卖出
* 要第 j 次买入,必须先有 j-1 次卖出;要第 j 次卖出,必须先有 j 次买入。
*/
public int maxProfitIII(int k, int[] prices) {
if (prices.length == 0) return 0;

// 优化:k 足够大时,等价于可以无限次交易,用贪心
if (k >= prices.length / 2) {
return maxProfitII(prices);
}

int[] buy = new int[k + 1];
int[] sell = new int[k + 1];

Arrays.fill(buy, Integer.MIN_VALUE); // 买入状态初始为负无穷(还没买入)
// sell 初始为 0(一次都没卖,利润 0)

for (int price : prices) {
for (int j = 1; j <= k; j++) {
buy[j] = Math.max(buy[j], sell[j - 1] - price);
sell[j] = Math.max(sell[j], buy[j] + price);
}
}
return sell[k];
}


附.完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
import java.util.Arrays;
import java.util.List;

public class DpTest {

// ---- 斐波那契数列 ----
public static int fib(int n) {
if (n == 0 || n == 1) return n;

int dp1 = 1, dp2 = 0;
int dp = 0;
for (int i = 2; i <= n; i++) {
dp = dp1 + dp2;
dp2 = dp1;
dp1 = dp;
}
return dp;
}


// ---- 找出最大的那个连续子序列的和 ----
public static int maxSubArraySum(int[] array) {
int dp = array[0];
int globalMax = array[0];

for (int i = 1; i < array.length; i++) {
dp = Math.max(dp + array[i], array[i]);
globalMax = Math.max(dp, globalMax);
}
return globalMax;
}


// ---- 最长的公共字串 I(不连续情况)----
public static String lcsString01(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];

// 填表
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (text1.charAt(i - 1) == text2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

// 回溯
StringBuilder sb = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
sb.append(text1.charAt(i - 1));
i--; j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return sb.reverse().toString();
}

// 最长的公共字串 II(连续情况)
public static String lcsString02(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m+1][n+1];
int maxLen = 0;
int endIndex = 0;

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i-1) == text2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
endIndex = i-1;
}
}
}
}
return text1.substring(endIndex-maxLen+1, endIndex+1);
}


// ---- 零钱兑换问题 ----
public static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;

for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i >= coin) {
dp[i] = Math.min(dp[i], dp[i-coin] + 1);
}
}
}

return dp[amount] > amount ? -1 : dp[amount];
}


// ---- 背包问题 I(0-1 背包)----
public static int knapsack01(int[] weight, int[] value, int capacity) {
int[] dp = new int[capacity+1];
for (int i = 0; i < weight.length; i++) {
for (int j = capacity; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);
}
}
return dp[capacity];
}

// 背包问题 II(完全背包)
public static int knapsack02(int[] weight, int[] value, int capacity) {
int[] dp = new int[capacity+1];
for (int i = 0; i < weight.length; i++) {
for (int j = weight[i]; j <= capacity; j++) {
dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);
}
}
return dp[capacity];
}

// 背包问题 III(多重背包)
public static int knapsack03(int[] weight, int[] value, int[] count, int capacity) {
int[] dp = new int[capacity+1];
for (int i = 0; i < weight.length; i++) {
int w = weight[i], v = value[i], c = count[i];
for (int k = 1; c > 0; k*=2) {
int take = Math.min(k, c);
c -= take;

int packW = take * w;
int packV = take * v;

for (int j = capacity; j >= packW; j--) {
dp[j] = Math.max(dp[j], dp[j-packW] + packV);
}
}
}
return dp[capacity];
}

// 背包问题 IV(分组背包)
static class Item {
int weight;
int value;
public Item(int weight, int value) {
this.weight = weight;
this.value = value;
}
}
public static int knapsack04(List<List<Item>> groups, int capacity) {
int[] dp = new int[capacity + 1];
for (List<Item> group : groups) {
for (int j = capacity; j >= 0; j--) {
for (Item item : group) {
if (j >= item.weight) {
dp[j] = Math.max(dp[j], dp[j - item.weight] + item.value);
}
}
}
}
return dp[capacity];
}


// ---- 股票最大收益 I(交易一次)----
public int maxProfitI(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price; // 更新历史最低价
} else {
maxProfit = Math.max(maxProfit, price - minPrice); // 尝试卖出
}
}
return maxProfit;
}

// 股票最大收益 II(交易多次)
public int maxProfitII(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}

// 股票最大收益 III(最多 k 次交易)
public int maxProfitIII(int k, int[] prices) {
if (prices.length == 0) return 0;

// 优化:k 足够大时,等价于可以无限次交易,用贪心
if (k >= prices.length / 2) {
return maxProfitII(prices);
}

int[] buy = new int[k + 1];
int[] sell = new int[k + 1];

Arrays.fill(buy, Integer.MIN_VALUE); // 买入状态初始为负无穷(还没买入)
// sell 初始为 0(一次都没卖,利润 0)

for (int price : prices) {
for (int j = 1; j <= k; j++) {
buy[j] = Math.max(buy[j], sell[j - 1] - price);
sell[j] = Math.max(sell[j], buy[j] + price);
}
}
return sell[k];
}
}