斐波那契数列
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
|
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
|
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
|
private static int fib(int n) { if (n == 0 || n == 1) return n;
int[] dp = new int[n+1]; 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
|
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
|
public static int countClimbTheStairs(int n) { if (n <= 2) return n;
int prevII = 1; int prevI = 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
|
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)); }
public static int maxSubArray(int[] nums) { int dp = nums[0]; int globalMax = nums[0];
for (int i = 1; i < nums.length; i++) { dp = Math.max(dp + nums[i], nums[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
| 字符相等:text1[i-1] == text2[j-1] 转移方程:dp[i][j] = dp[i-1][j-1] + 1
字符不等: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); }
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
|
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]); } } } 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;
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 2
| 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]; 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]; }
|
背包问题
背包问题是动态规划里最大、最系统的一个家族。什么是背包问题呢?就是给你一堆物品,每个物品有重量和价值。给你一个容量有限的背包。问:怎么选物品,使得总重量不超过背包容量,且总价值最大?不同变体区别就在于:每个物品能选几次。
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
|
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][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;
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];
for (List<Item> group : groups) { for (int j = W; 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[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
|
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
|
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
|
public int maxProfitIII(int k, int[] prices) { if (prices.length == 0) return 0;
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);
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; }
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(); }
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]; }
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]; }
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]; }
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]; }
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]; }
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; }
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; }
public int maxProfitIII(int k, int[] prices) { if (prices.length == 0) return 0;
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);
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]; } }
|