最近发现笔试题的区分度主要在动态规划，本文按照题型归类整理。
背包问题
0-1 背包问题
给定一组物品，每个物品有两个属性：重量（w）和价值（v）。同时给定一个背包的容量（bag）。目标是选择一些物品放入背包中，使得在不超过背包容量的前提下，物品的总价值最大。在01背包问题中，每个物品只能选择放入背包一次（要么放入，要么不放入），不能重复放入。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static int bag01(int[] w, int[] v, int bag) {
int N = w.length;
// 对于前 i 个物品可能的选择，若背包剩余容量为 j，能达到的最大价值为 dp[i][j]
// i 属于 [0,N]
// rest 属于 [0,bag]
int[][] dp = new int[N + 1][bag + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= bag; j++) {
// w[i-1] v[i-1] 表示第 i 件物品的重量和价值
int wi = w[i - 1], vi = v[i - 1];
// 不选择第 i 件物品
int p1 = dp[i - 1][j];
// 选择第 i 件物品,要看背包剩余容量是否能放下物品 i
int p2 = j >= wi ? dp[i - 1][j - wi] + vi : 0;
dp[i][j] = Math.max(p1, p2);
}
}
// 对于所有（N个）物品，背包容量为 bag 时的最大价值
return dp[N][bag];
}
|
- 时间复杂度：O(N x bag)
- 空间复杂度：O(N x bag)
其中N为物品的数量，bag为背包的容量。
WY 厂笔试
将 nums 数组分成两部分，使得每一部分都包含至少一个元素，并且元素之和相加大于 k。
转换思路：从nums中选取1～N-1个元素，使得他们的和在一定范围[k,sum-k]内
再·转换思路 ：0-1 背包问题，背包大小范围在[k,sum-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
| public static int countPartitionsBag(int[] nums, int k) {
int sum = 0;
for (int num : nums) {
sum += num;
}
// 下界大于上界
if (k > sum - k) {
return 0;
}
// 转换成 0-1 背包问题，背包最大容量为 sum-k，每个数的重量为数值，价值上一状态的价值
// 在计算过程中 背包容量从 1～sum-k 的情况都一并计算了，涵盖了[k,sum-k]
int N = nums.length;
int bag = sum - k;
int[][] dp = new int[N + 1][bag + 1];
dp[0][0] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= bag; j++) {
// nums[i-1] 表示第 i 个数(的重量)
int wi = nums[i - 1];
// 默认不选择
dp[i][j] = dp[i-1][j];
// 选择,要看背包剩余容量是否能放下
dp[i][j] +=j >= wi ? dp[i - 1][j - wi] : 0;
}
}
// 统计背包范围在 [k,sum-k] 的情况数
int res = 0;
for (int i = k; i <= sum - k; i++) {
res += dp[N][i];
}
return res;
}
|
子集背包问题
给定一个非空数组 nums，判断数组是否可以被分割成两个子集，使两个子集元素和相等。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public static boolean canPartition(int[] nums) {
int sum = 0, n = nums.length;
for (int num : nums) {
sum += num;
}
if ((sum & 1) == 1) {
return false;
}
sum /= 2;
boolean[] dp = new boolean[sum + 1];
dp[0] = true;
for (int num : nums) {
// 从后往前遍历，防止前面的的结果影响后面
for (int i = sum; i >= 0; i--) {
// 选择是否使用 num 来组成剩下的和
if (i - num >= 0) {
dp[i] = dp[i] || dp[i - num];
}
}
}
return dp[sum];
}
|
完全背包问题
物品的数量无限，求刚好装满背包的组合数。
[322]零钱兑换.java
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static int coinChange(int[] coins, int amount) {
// 要凑到 i 元钱有 dp[i] 种情况
int[] dp = new int[amount + 1];
// 不赋值 Integer.MAX_VALUE 是担心 +1 溢出
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
// 目标金额通过这一个硬币，与【目标-硬币】金额联系起来，选择硬币数更少的情况
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
|
股票问题
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
lv1. 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int maxProfit(int[] prices) {
int res = 0;
int min = Integer.MAX_VALUE;
for (int price : prices) {
if (price <= min) {
min = Math.min(min, price);
} else {
res = Math.max(res, price - min);
}
}
return res;
}
}
|
lv2. 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) {
return 0;
}
int res = 0;
int pre = prices[0];
for (int i = 1; i < prices.length; i++) {
int cur = prices[i];
if (cur > pre) {
res += cur - pre;
}
pre = cur;
}
return res;
}
}
|
lv3. 每次交易（买入+卖出）需要交手续费
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int[][] dp = new int[n][2];
// 0 不持有 1 持有
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < n; i++) {
// i-1 昨天
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[n - 1][0];
}
}
|
lv4. 不限次数，但含冷冻期：卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
if (n <= 1) return 0;
// 0 不持有，不在冷冻期
// 1 持有
// 2 不持有，在冷冻期 - 昨天一定持有，且今天要卖
int[][] dp = new int[n][3];
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
for (int i = 1; i < n; i++) {//从[1]...[n-1]
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = dp[i - 1][1] + prices[i];
}
return Math.max(dp[n - 1][0], dp[n - 1][2]);
}
}
|
lv5. 最多可以完成 两笔 交易，不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
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
| class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) {
return 0;
}
int n = prices.length;
int[][] dp = new int[n][5];
// 0 没有任何买卖
// 1 买入第一次
dp[0][1] = -prices[0];
// 2 卖出第一次
// 3 买入第二次
dp[0][3] = -prices[0];
// 4 卖出第二次
for (int i = 1; i < n; i++) {
// i-1 表示昨天
// 买入花钱，所以是 -price[i]
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
// 卖出得钱，所以是 +price[i]
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
// 最后一天的第二次卖出
return dp[n - 1][4];
}
}
|
lv6. 你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 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
| class Solution {
public int maxProfit(int k, int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
// 0 未买入
// k+1 第 k 次买入 - 奇数
// k+2 第 k 次卖出 - 偶数
int[][] dp = new int[len][2 * k + 1];
// 每个时刻第一次买入的初始情况
for (int i = 0; i < k; i++) {
dp[0][2 * i + 1] = -prices[0];
}
for (int i = 1; i < len; i++) {
// i-1 表示昨天
for (int j = 1; j <= 2 * k; j++) {
if ((j & 1) == 1) {
// 当天考虑买入
// 不买，延续昨天的
// 买，要在昨天不持有的基础上买
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
} else {
// 当天考虑卖出
// 不卖，延续昨天的
// 卖，要在昨天持有的基础上卖
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
}
}
}
return dp[len - 1][2 * k];
}
}
|
lv999. 限制K笔交易，冷冻期1天，有手续费？
字符串比较问题
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int longestCommonSubsequence(String text1, String text2) {
int n1 = text1.length(),n2 =text2.length();
int[][] dp = new int[n1+1][n2+1];
for(int i=1;i<=n1;i++){
int char1 = text1.charAt(i-1);
for(int j=1;j<=n2;j++){
int char2 = text2.charAt(j-1);
if(char1==char2){
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[n1][n2];
}
|
编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
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
| public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
// 多开一行一列是为了保存边界条件，即字符长度为 0 的情况，这一点在字符串的动态规划问题中比较常见
int[][] dp = new int[len1 + 1][len2 + 1];
// 初始化：当 word2 长度为 0 时，将 word1 的全部删除即可
for (int i = 1; i <= len1; i++) {
dp[i][0] = i;
}
// 当 word1 长度为 0 时，插入所有 word2 的字符即可
for (int j = 1; j <= len2; j++) {
dp[0][j] = j;
}
char[] word1Array = word1.toCharArray();
char[] word2Array = word2.toCharArray();
// 递推开始，注意：填写 dp 数组的时候，由于初始化多设置了一行一列，横纵坐标有个偏移
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
// 这是最佳情况
if (word1Array[i - 1] == word2Array[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
continue;
}
// 否则在以下三种情况中选出步骤最少的，这是「动态规划」的「最优子结构」
// 1、在下标 i 处插入一个字符
int insert = dp[i][j - 1] + 1;
// 2、替换一个字符
int replace = dp[i - 1][j - 1] + 1;
// 3、删除一个字符
int delete = dp[i - 1][j] + 1;
dp[i][j] = Math.min(Math.min(insert, replace), delete);
}
}
return dp[len1][len2];
}
|
都将会