背包问题
279. 完全平方数
可以看作物品重量为完全平方数的完全背包问题。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
for (int i=0; i<=n; i++) {
dp[i] = i;
for (int j=1; j*j<=i; j++) {
dp[i] = Math.min(dp[i], dp[i-j*j]+1);
}
}
return dp[n];
}
}
|
322. 零钱兑换
dp[i]表示当零钱总数为i时所需最少的硬币数。将dp[i]的值初始化为一个不可能取到的值以表示无法组成总金额。状态转移方程：dp[i]=min(dp[i], dp[i-coin]+1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i=1; i<=amount; i++) {
for (int coin: coins) {
if (i<coin || dp[i-coin]==Integer.MAX_VALUE) continue;
dp[i] = Math.min(dp[i], dp[i-coin]+1);
}
}
return dp[amount]>amount? -1: dp[amount];
}
}
|
416. 分割等和子集
本题是求是否存在子数组之和为数组总和的一半，可使用动态规划解决此类0-1背包问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public boolean canPartition(int[] nums) {
int sum = 0, maxNum = 0;
for (int num: nums) sum += num;
if (sum%2==1) return false;
int target = sum/2;
boolean[] bag = new boolean[target+1];
bag[0] = true;
for (int num: nums) {
for (int i=target; i>=0; i--) {
if (i>=num) bag[i] |= bag[i-num];
}
}
return bag[target];
}
}
|
494. 目标和
方法一：深度优先搜索
穷举每一个元素取正负符号的所有组合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
int res;
int[] nums;
public int findTargetSumWays(int[] nums, int S) {
this.nums = nums;
dfs(0, S);
return res;
}
public void dfs(int i, int sum) {
if (i==nums.length) {
if (sum==0) res++;
return;
}
dfs(i+1, sum+nums[i]);
dfs(i+1, sum-nums[i]);
}
}
|
方法二：动态规划
本题是求数组中一部分元素之和减去其它元素之和等于S，即part1 - part2 == S，而part1 + part2 == sum，因此2 * part1 == S + sum，从而转化为求和为(sum + S) / 2的0-1背包问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int num: nums) sum += num;
if ((sum+S)%2==1 || S>sum) return 0;
int target = (sum + S) / 2;
int[] dp = new int[target+1];
dp[0] = 1;
for (int num: nums) {
for (int i = target; i>=num; i--) {
dp[i] += dp[i-num];
}
}
return dp[target];
}
}
|
“股票交易”问题
121. 买卖股票的最佳时机
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int maxProfit(int[] prices) {
if (prices.length==0) return 0;
int min = prices[0];
int profit = 0;
for (int i=0; i<prices.length; i++) {
min = Math.min(min, prices[i]);
profit = Math.max(profit, prices[i]-min);
}
return profit;
}
}
|
309. 最佳买卖股票时机含冷冻期
dp[i][j]表示第i天所能获得的最大收益，j表示当天最终是否持有股票。第i天未持有股票（dp[i][0]），可能是第i-1天也未持有，也可能是第i-1天持有但今日卖出。状态转移方程：dp[i][0]=max(dp[i-1][0], dp[i-1][1]+prices[i])；第i天持有股票（dp[i][1]），可能是第i-1天未持有但今日买入，也可能是第i-1天就持有今日未卖出。这里因为有冷却期，因此若今日买入，昨日不能卖出，此状态只与前一日有关。状态转移方程：dp[i][1]=max(dp[i-1][1], dp[i-2][0]-prices[i])。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int maxProfit(int[] prices) {
if (prices.length==0) return 0;
int dp[][] = new int[prices.length+1][2];
dp[0][0] = 0;
dp[1][0] = 0;
dp[1][1] = -1 * prices[0];
for (int i=2; i<=prices.length; i++) {
dp[i][1] = Math.max(dp[i-2][0]-prices[i-1], dp[i-1][1]);
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i-1]);
}
return dp[prices.length][0];
}
}
|
“打家劫舍”问题
198. 打家劫舍
状态转移方程：dp[i] = max(dp[i-2]+nums[i], dp[i-1])。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int rob(int[] nums) {
if (nums.length==0) return 0;
if (nums.length==1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(dp[0], nums[1]);
for (int i=2; i<nums.length; i++) {
dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
}
return dp[nums.length-1];
}
}
|
337. 打家劫舍 III
对每个结点有两种选择：偷或不偷。如果选择偷这个节点，那么可能获得的最大收益等于这个节点的收益加上不偷两个子节点的最大收益；如果选择不偷这个节点，那么可能的最大收益等于两个子节可偷可不偷的最大收益的和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int rob(TreeNode root) {
int[] res = robber(root);
return Math.max(res[0], res[1]);
}
public int[] robber(TreeNode root) {
if (root==null) return new int[]{0, 0};
int[] money = new int[2];
int[] left = robber(root.left);
int[] right = robber(root.right);
money[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
money[1] = root.val + left[0] + right[0];
return money;
}
}
|