姓名：谭旭东 学号：19011210016
前言
- 动态规划是什么？
-
动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。
-
动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
-
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。
-
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
- 如何学习动态规划？
- 多刷题，掌握该算法的整体思路
- 在接下来的内容中，我将通过不同的【转移方程】将动态规划的题目进行分类，让我们对不同类型的题目有更好的认识
一、简单相加的状态转移
这类动态规划属于比较简单的情况，因为转移方程可以简单的直接得到
而且由于新状态转移只需要前几个状态，我们可以压缩状态来节省更多空间
1. 斐波那契数列
- 题目出处：509. 斐波那契数
- 转移方程：【F(n) = F(n - 1) + F(n - 2)】
- 初始状态：【F(0) = 0，F(1) = 1】
不使用状态压缩：
public int fib(int n) {
if (n == 0) return 0;
if ( n == 1 || n == 2) return 1;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i<=n; i++) {
dp[i] = f0 + f1;
}
return dp[n];
}
状态压缩后：
public int fib(int n) {
if (n == 0) return 0;
if ( n == 1 || n == 2) return 1;
int f0 = 0;
int f1 = 1;
for (int i = 1; i<n; i++) {
int newf = f0 + f1;
f0 = f1;
f1 = newf;
}
return f1;
}
2. 第 N 个泰波那契数
- 题目出处：1137. 第 N 个泰波那契数
- 转移方程：【Tn+3 = Tn + Tn+1 + Tn+2】
- 初始状态：【T0 = 0，T1 = 1，T2 = 1】
直接上状态压缩之后的代码
public int tribonacci(int n) {
if ( n == 0 ) return 0;
if ( n <= 2) return 1;
int t0 = 0;
int t1 = 1;
int t2 = 1;
for (int i = 3; i <= n; i++) {
int newT = t0 + t1 + t2;
t0 = t1;
t1 = t2;
t2 = newT;
}
return t2;
}
3. 爬楼梯
- 题目出处：70. 爬楼梯
- 转移方程：【dp[n] = dp[n-1] + dp[n-2]】
- 初始状态：【dp[1] = 1，dp[2] = 2】
状态压缩后的代码：
public int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int dp1 = 1;
int dp2 = 2;
for (int i = 3; i <= n; i++) {
int newDp = dp1 + dp2;
dp1 = dp2;
dp2 = newDp;
}
return dp2;
}
二、取max/min的状态转移
这种状态转移方程需要在转移过程中选取最小/最大值
1. 最小花费爬楼梯
- 题目出处：746. 使用最小花费爬楼梯
- 状态转移：【dp[i] = min{ dp[i-1]+cost[i-1] , dp[i-2]+cost[i-2]}】
- 分析：能够从第i-1个台阶爬到本台阶，也能从第i-2个台阶爬到本台阶；爬的时候分别加上对应的cost即可
- 初始状态：【dp[0] = 0 , dp[1] = 1】
只需要前两个状态，所以还是可以状态压缩（注释掉的是没进行状态压缩的版本）
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
if (len == 1) return 0;
if (len == 2) return Math.min(cost[0],cost[1]);
// int[] dp = new int[len + 1];
int dp1 = 0;
int dp2 = 0;
for (int i = 2; i<=len; i++) {
// dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
int newdp = Math.min(dp1+cost[i-2],dp2+cost[i-1]);
dp1 = dp2;
dp2 = newdp;
}
// return dp[len];
return dp2;
}
2. 打家劫舍
- 题目出处：198. 打家劫舍
- 转移方程：【dp[i] = max{dp[i-2] + nums[i] , dp[i-1]}】
- 分析：因为不能连着抢劫，所以可以【抢第i-2家和第i家的，那么收益为dp[i-2] + nums[i]】，或者【第i家的不抢，那么收益仍未dp[i-1]】
- 初始状态：【dp[0] = nums[0]，dp[1] = max{nums[0]，nums[1]}】
代码如下，状态压缩版本（注释掉的是非状态压缩版）
public int rob(int[] nums) {
int len = nums.length;
if (len == 1) return nums[0];
if (len == 2) return Math.max(nums[0],nums[1]);
// int[] dp = new int[len];
// dp[0] = nums[0];
// dp[1] = Math.max(nums[0],nums[1]);
int dp0 = nums[0];
int dp1 = Math.max(nums[0],nums[1]);
for (int i = 2; i < len; i++) {
// dp[i] = Math.max(dp[i-1] , dp[i-2] + nums[i]);
int newDp = Math.max(dp1 , dp0 + nums[i]);
dp0 = dp1;
dp1 = newDp;
}
// return dp[len-1];
return dp1;
}
3. 打家劫舍2
- 题目出处：213. 打家劫舍 II
- 状态转移：和上题一致
- 初始状态：和上题一致
不同点在于：这里的房屋（数组）是首尾相连的，也就是说打劫了第一家，就不能打劫最后一家；打劫了最后一家，就不能打劫第一家
根据这种情况，我们将数组分为nums[0,len-1]和nums[1,len]，然后分别通过上一题的方式进行求解，然后返回两个解的最大值即可
代码如下
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
if (n == 2) return Math.max(nums[0],nums[1]);
int[] nums1 = Arrays.copyOfRange(nums , 0 , n - 1);
int[] nums2 = Arrays.copyOfRange(nums , 1 , n);
int ans1 = findMax(nums1);
int ans2 = findMax(nums2);
return Math.max(ans1 , ans2);
}
public int findMax(int[] nums) {
int n = nums.length;
if (n == 2) return Math.max(nums[0] , nums[1]);
int dp0 = nums[0];
int dp1 = Math.max(nums[0],nums[1]);
for (int i = 2 ; i < n; i++) {
int newdp = Math.max(dp1,dp0 + nums[i]);
dp0 = dp1;
dp1 = newdp;
}
return dp1;
}
4. 删除并获得点数
-
题目出处：740. 删除并获得点数
-
状态转移：【dp[i] = max{ dp[i-1] , dp[i-2] + count[i]*i }】
- ① 这里我们将题目转换一种思路，相当于打家劫舍的进阶版，也就是说我们不能够选择相邻的元素
- ② 我们需要先得到nums[]数组中的最大值max，然后将nums[]数组转换成为count[]数组，统计每个数字出现的次数（count[]数组的大小为【max+1】，从1~max）
- ③ 然后我们开始状态转移过程：可以从i-1状态转移到目前状态，由于不能够连着选数字，所以这种情况下收益为【dp[i-1]】；或者从i-2状态转移到目前状态，那么目前状态是可以选上的，所以当前收益为【dp[i-2] + count[i] * i】
-
初始状态：
- dp[1] = count[1] * 1
- dp[2] = max{count[1] * 1，count[2] * 2}
代码如下：
public int deleteAndEarn(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
}
if (max == 1) return nums.length;
int[] count = new int[max + 1];
int[] dp = new int[max + 1];
for (int i = 0; i < nums.length; i++) {
++count[nums[i]];
}
dp[1] = count[1];
dp[2] = Math.max(count[1], count[2] * 2);
for (int i = 3; i <= max; i++) {
dp[i] = Math.max(dp[i - 2] + count[i] * i, dp[i - 1]);
}
return dp[max];
}
三、嵌套的状态转移
这种DP的状态转移，会和之前的所有状态有关，不可进行状态压缩
1. 跳跃游戏2
- 题目出处：45. 跳跃游戏 II
- 状态转移：dp[i]表示跳到i位置所需的最小步数
- ① 求dp[i]时，目前状态的值和之前的所有状态值都有关
- ② 遍历之前所有的节点，如果不能跳到本节点，则跳过
- ③ 如果j节点能够跳到本节点，即【j + nums[j] >= i】
- ④ 对所有能够跳到本节点的前置j节点，推导得到【dp[i] = min{dp[i],dp[j]+1}】
- 初始状态：
- ① dp[0] = 0;
- ② 其他节点假设不可达，设置成为Integer.MAX_VALUE
动态规划版本的代码如下：
public int jump(int[] nums) {
int len = nums.length;
if (len == 1) return 0;
int[] dp = new int[len];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (j + nums[j] >= i)
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
return dp[len - 1];
}
其实该题目还能用BFS去做，不断对节点松弛，有点类似于SPFA算法，代码如下：
public int jump(int[] nums) {
int len = nums.length;
int[] d = new int[len];
Arrays.fill(d, Integer.MAX_VALUE);
d[len - 1] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.offer(len - 1);
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int i = 0; i < len; i++) {
if (nums[i] >= cur - i) { // 判断能否到达
if (d[cur] + 1 < d[i]) { // 是否松弛成功，成功才入队
d[i] = d[cur] + 1;
queue.add(i);
}
}
}
}
return d[0];
}
四、连续子数组状态转移
这类题目往往要求连续子数组的最大/最小和值，我们在遍历数组时通过一个sum（子数组和）值不断更新最大/最小值，最后可以得到结果
1. 最大子序和
-
题目出处：53. 最大子序和
-
状态转移：
- ① 设置一个sum值，作为我们目前的子数组和
- ② 遍历数组，我们需要求的是最大值，那么我们可以很简单的分析出，最大子数组肯定不是以负数开头或者结尾的（除非只有负数）
- ③ 再进一步推导，如果前置的某个子数组为负数，我们可以将它合并，那么它对我们接下来需要寻找的最大值是没有一点正面的帮助的，需要舍弃掉，继续从当前位置开始往下找
- ④ 也就是说，如果【sum <= 0】，那么我们从当前位置往下找即【sum = nums[i]】
- ⑤ 如果【sum > 0】，那么不管【nums[i]】是正还是负，我们都可以把它加到我们的子数组中去
- ⑥ 为什么负数还要加进去？是因为可能出现一个很小的负数，但是前面的正数却很大的情况，如[100,-1,100]；如果遇到负数我们就重新开始的话，是有可能出现捡了芝麻丢了西瓜的情况的
- ⑦ 如果前面的正数很小，而负数却很大的话，如[-100,1,1]；那么这种情况我们通过④就能够切断掉前面的很大的负数
要用语言表达思路，实在是...
还是直接上代码把，要去品...
public int maxSubArray(int[] nums) {
int ans = Integer.MIN_VALUE;
int sum = 0;
for(int i=0; i< nums.length; i++) {
if (sum <= 0) {
sum = nums[i];
} else {
sum += nums[i];
}
ans = Math.max(ans , sum);
}
return ans;
}
2. 环形子数组的最大和
思路：其实和上题基本一致，但是由于这里是首尾相连，我们需要分情况讨论
- （1）最大和子数组出现在中间：
- ① 这种情况，包含了首尾都不选（首尾都为负），或者首尾只选一个的情况（首尾其中一个为负）
- ② 如果全都是正数，那么这种情况还包含了首尾都选的情况
- ③ 我们可以直接通过上一题的思路，求出这种情况下的最大值max
- （2）最大子数组和出现在两端：
- ① 这种情况的意思是，最大子数组同时包含了首尾元素，还可能往数组中间延申
- ② 假设整个数组所有数的和为sum
- ③ 如果两端的和是最大的，那么中间的和就是最小的！
- ④ 我们只需要按照上一题的逻辑，在数组中间求出连续数组的最小值和值min，最后【sum - min】就是数组剩下元素的最大和值
代码：注意，求第二种情况需要去掉首尾元素！
public int maxSubarraySumCircular(int[] nums) {
if (nums.length == 1) return nums[0];
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int sum1 = 0;
int sum2 = 0;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum1 <= 0)
sum1 = nums[i];
else
sum1 += nums[i];
max = Math.max(max, sum1);
}
for (int i = 1; i < nums.length - 1; i++) {
if (sum2 >= 0)
sum2 = nums[i];
else
sum2 += nums[i];
min = Math.min(min, sum2);
}
return Math.max(sum - min, max);
}
3. 乘积最大的子数组
-
题目出处：152. 乘积最大子数组
-
转移方程：【preMax = max{preMax * nums[i]，preMin * nums[i]}】，【preMin = min{preMax * nums[i]，preMin * nums[i]}】
- ① 由于数组中的元素有正有负，负数的存在可能会导致最大值max变最小值min，最小值min变最大值
- ② 所以在寻找子序列的过程中，维护最大值preMax和最小值preMin，表示前缀最大/最小值
- ③ 还需要考虑一种情况即【nums[i] = 0】，后面的乘积都为0了，需要从下一个数开始继续取，这种情况下我们下一次的preMax和preMin直接从nums[i+1]开始
-
初始状态：【preMax = nums[0]】【preMin = nums[0]】
public int maxProduct(int[] nums) {
int max = nums[0];
// 前置最大最小乘积
int preMax = nums[0];
int preMin = nums[0];
int len = nums.length;
for (int i = 1; i < len; i++) {
/**
* 当前的最大最小值
* 可能由前置的最大最小值乘以正数/负数得到
*/
int curMax = Math.max(preMax * nums[i], preMin * nums[i]);
int curMin = Math.min(preMax * nums[i], preMin * nums[i]);
/**
* 是0的情况，会从nums[i+1]重新开始
* 所以我们需要加入以下语句，以免curMax和curMin都为0
* 之后乘积就全部为0了
*/
preMax = Math.max(nums[i], curMax);
preMin = Math.min(nums[i], curMin);
max = Math.max(preMax, max);
}
return max;
}
4. 乘积为正数的最长子数组
-
题目出处：1014. 最佳观光组合
-
转移方程：
- ① 乘积要为正数，那么同上一题一样，根据nums[i]的不同情况分类，我们需要维护两个数组postive[i]和negative[i]，分别表示以nums[i]结尾的子数组，前面连续最长的正数/负数乘积为多少
- ② 如果【nums[i] = 0】，那么子数组需要从下一个开始进行计算，即【postive[i] = 0】【negative[i] = 0】
- ③ 如果【nums[i] > 0】，那么【postive[i] = postive[i-1] + 1】，【negative[i] = negative[i-1] + 1】（特殊情况：如果negative[i-1] = 0，说明前面子数组长度为0，那么【negative[i] = 0】）
- ④ 如果【nums[i] < 0】，那么【negative[i] = negative[i-1] + 1】，【positive[i] = negative[i-1] + 1】（特殊情况：如果negative[i-1] = 0，说明前面子数组长度为0，那么【positive[i] = 0】）
-
初始状态：
- nums[0]大于0时，将positive[0]置1
- nums[0]小于0时，将negative[0]置1
public int getMaxLen(int[] nums) {
int len = nums.length;
int[] pos = new int[len];
int[] neg = new int[len];
// 初始化
if (nums[0] > 0) pos[0] = 1;
else if (nums[0] < 0) neg[0] = 1;
int max = pos[0];
for (int i = 1; i < len; i++) {
if (nums[i] > 0) {
pos[i] = pos[i - 1] + 1;
neg[i] = neg[i - 1] == 0 ? 0 : neg[i - 1] + 1;
} else if (nums[i] < 0) {
pos[i] = neg[i - 1] == 0 ? 0 : neg[i - 1] + 1;
neg[i] = pos[i - 1] + 1;
} else {
pos[i] = 0;
neg[i] = 0;
}
max = Math.max(max, pos[i]);
}
return max;
}
5. 最佳观光组合
-
状态转移：观光得分：【values[i] + values[j] + i - j】
- ① 将上述得分拆分成为两个部分，对于j位置来说，我们只需要知道前置最大的【values[i] + i】即可
- ② 通过记录max{values[i] + i}，然后遍历数组，我们可以只进行一次遍历就求得结果
-
初始状态：【maxVi = values[0] + 0】
其实这题的总体思路就是在遍历过程中维护一个最大值
代码如下：
public int maxScoreSightseeingPair(int[] values) {
int ans = 0;
int maxVi = values[0] + 0;
for (int j = 1; j < values.length; j++) {
ans = Math.max(ans , maxVi + values[j] - j);
if (values[j] + j > maxVi)
maxVi = (values[j] + j);
}
return ans;
}
五、 买卖股票问题
这类题目模拟股票的买入和卖出，其实就是要我们对股票的状态进行一个模拟，实现完整的过程并且将所有结果模拟出来进行对比
1. 买卖股票的最佳时机
- 题目出处：121. 买卖股票的最佳时机
- 一支股票，一买一卖（也可以不买）
- 状态转移：维护二维数组dp[prices.length][2]
- ① 第一层状态i表示到第i天能够获得的最大收益
- ② 第二层状态标识该天股票的持有情况，0表示未持有，1表示已持有
- ③ 当前未买入状态【dp[i][0]】可以由两种状态转移而来，取两者最大值
- 前一天也未持有：【dp[i-1][0]】
- 前一天已经持有，今天卖出：【dp[i-1][1] + price[i]】
- ④ 当前买入状态【dp[i][1]】可以由两种状态转移而来
- 前一天已经持有：【dp[i-1][1]】
- 前一天未持有，今天买入：【dp[i-1][0] - price[i]】（需要更改）
- 注意：<font color=red>这里由于我们只能单次买入卖出股票，所以买入股票这个操作是无前效性的，我们需要更改最后一种状态为【-price[i]】</font>
- 初始状态：
- 【dp[0][0] = 0】
- 【dp[0][1] = -prices[0]】（第一天就买入）
代码：
public int maxProfit(int[] prices) {
int len = prices.length;
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i<len; i++) {
dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1] , -prices[i]);
}
return dp[len - 1][0];
}
2. 买卖股票的最佳时机2
-
题目出处：122. 买卖股票的最佳时机 II
-
状态转移：一次只能持有一支股票，可以多次买卖
- 上一题已经分析得到这个的转移状态方程了
- 【dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] + prices[i])】
- 【dp[i][1] = Math.max(dp[i-1][1] , dp[i-1][0] - prices[i])】
public int maxProfit(int[] prices) {
int len = prices.length;
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i<len; i++) {
dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1] , dp[i-1][0] - prices[i]);
}
return dp[len - 1][0];
}
3. 最佳买卖股票时机含冷冻期
-
题目出处：309. 最佳买卖股票时机含冷冻期
-
状态转移：加入冷冻期，时长为1天，也就是说前一天卖出股票，后一天无法再买入；一次最多持有一支股票，可以多次买入卖出
- ① 维护转移数组dp[n][2]，n为天数，0表示未持有非冷冻期，1表示持有，2表示未持有但是处在冷冻期内
- ② 今天不持有股票且非冷冻期：前一天也不持有，分为两种情况，前一天是冷冻期和前一天不是冷冻期；所以【dp[i][0] = max{dp[i-1][0]，dp[i-1][2]}】
- ③ 今天持有股票：前一天也持有股票，或者前一天不持有股票，今天买入股票；所以【dp[i][1] = max{dp[i-1][1]，dp[i-1][0]-price[i]}】
- ③ 今天持有股票且在冷冻期内：前一天持有股票，且卖出；所以【dp[i][2] = dp[i-1][1] + price[i]】
-
初始状态：第一天肯定是没有冷冻期的
- dp[0][0] = 0
- dp[0][1] = -price[0]
- dp[0][2] = 0
public int maxProfit(int[] prices) {
int len = prices.length;
int[][] dp = new int[len][3];
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
for (int i = 1; i < len; i++) {
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[len - 1][0], Math.max(dp[len - 1][1], dp[len - 1][2]));
}
4. 买卖股票的最佳时机含手续费
-
题目出处：714. 买卖股票的最佳时机含手续费
-
转移方程：一次最多购买一支股票，可以多次买入卖出；每次交易（买入+卖出）都需要支付一定的手续费，其实也可以理解为卖出要收钱
- ① 正常转移，加上手续费即可
- ② 【dp[i][0] = max{dp[i-1][0]，dp[i-1][1] + price[i] - fee}】
- ③ 【dp[i][1] = max{dp[i-1][1]，dp[i-1][0] - price[i]}】
-
初始状态：dp[0][0] = 0，dp[0][1] = -price[0]
public int maxProfit4(int[] prices, int fee) {
int len = prices.length;
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; i++) {
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[len - 1][0];
}
六、0-1背包问题
基本概念：
- 最基本的背包问题就是 01 背包问题：一共有 N 件物品，第 i（i 从 1 开始）件物品的重量为 w[i]，价值为 v[i]。在总重量不超过背包承载上限 W 的情况下，能够装入背包的最大价值是多少？
- <font color=red>如果是 01 背包，即数组中的元素不可重复使用，外循环遍历 arrs，内循环遍历 target，且内循环倒序</font> （因为这里nums中一个元素只能用一次，循环过了就相当于取用过了，不再选了）
1. 分割等和子集
-
题目出处：416. 分割等和子集
-
思路：只要找到一个子集，其和刚好为sum/2即可
- ① 我们维护一个【dp[n+1]】数组，表示从0~n的数是否可以由nums数组中的数组成（这里n=sum/2）
- ② 外层循环nums，嵌套内循环倒序遍历dp[i]，在nums中找能够组成i的集合是否存在；也就说说我们一个一个数取出来，然后看这个数在范围 [0-target]内，能和前面已存在的结果构成什么新的结果。
- ③ 【dp[i] = dp[i] || dp[i - num]】，之所以要或上一个dp[i]，是因为结果具有前效性，也就是说如果早就拼凑出来了这个子集，要覆盖后面的结果使其为true
public boolean canPartition(int[] nums) {
int len = nums.length;
int sum = 0;
for (int i = 0; i < len; i++) sum += nums[i];
if (sum % 2 == 1) return false; // 奇数无法二分
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int i = target; i >= num; --i) {
if (i - num >= 0) {
dp[i] = dp[i] || dp[i - num];
}
}
}
return dp[target];
}
2. 目标和
-
题目出处：494. 目标和
- 题目的不同之处在于：选择数字的时候可以进行加或者减，所以我们维护的数组长度需要大于target了，至少得是数组和【sum】
-
思路1：我们想办法把这一题转换为上一题的思路，分析一下有什么不同
- ① 首先，所有的数字都一定要用上一次，去构建目标和
- ② 其次，使用该数字的时候可以选择其前面的符号为正或者负
- ③ 我们假设【target = x - y】，即x为正数部分总和，y为负数部分总和
- ④ 同时可以得到【sum = x + y】，也就是整体总和
- ⑤ 【（target + sum）/2 = x】，<font color=red>也就是说我们只要在数组中找到一个子数组，其和为x，构成正数部分，那么剩下的和就为y，构成负数部分</font>
- ⑥ 经过上述分析，我们将target转换为x，就可以套用上一题的思路
public int findTargetSumWays(int[] nums, int target) {
int len = nums.length;
int sum = 0;
for (int i = 0; i < len; i++) sum += nums[i];
if (target > sum || target < -sum || (target + sum) % 2 == 1) return 0;
int x = (sum + target) / 2;
int[] dp = new int[x + 1];
dp[0] = 1; // 目标和为0，可以不选，故总共有一种方案
for (int num : nums) {
for (int i = x; i >= num; --i) {
dp[i] += dp[i - num];
}
}
return dp[x];
}
- 思路2：当然还有一种做法，即扩大范围进行统计[-sum，sum]，然后每次状态转移时加上正负两种情况
- ① 维护二维数组dp[i][j]，其中i表示只考虑前i个数数字（数字需要全部用完），j表示能够构成结果为j的方案数量
- ② 其中i的范围为[0，len+1]，j的范围为[-sum，sum]
- ③ 由于是0-1背包问题，所以外层循环取num，内层循环更新方案数量，需要同时考虑加减两种方案
public int findTargetSumWays2(int[] nums, int target) {
int len = nums.length;
int sum = 0;
for (int i = 0; i < len; i++) sum += nums[i];
if (target > sum || target < -sum) return 0;
// i表示使用了前几个数组num
// j表示能够构成的结果，范围为-sum到sum，下面使用时需要加入偏移量
int[][] dp = new int[len + 1][sum * 2 + 1];
dp[0][sum] = 1; // 使用0个元素构成0，方案有一种
for (int i = 1; i <= len; i++) {
int num = nums[i - 1];
for (int j = -sum; j <= sum; j++) {
if (j + sum - num >= 0)
dp[i][j + sum] += dp[i - 1][j + sum - num];
if (j + sum + num <= 2 * sum)
dp[i][j + sum] += dp[i - 1][j + sum + num];
}
}
// 所有数都用上，能构成target的方案数量
return dp[len][target + sum];
}
七、完全背包问题
基本概念：
- 完全背包与 01 背包不同就是每种物品可以有无限多个：一共有 N 种物品，每种物品有无限多个，第 i（i 从 1 开始）种物品的重量为 w[i]，价值为 v[i]。在总重量不超过背包承载上限 W 的情况下，能够装入背包的最大价值是多少？
- 一般就是要我们在arr[]数组中找出能够组成target的组合
- （1）如果是完全背包，即数组中的元素可重复使用并且不考虑元素之间顺序，arrs 放在外循环（保证 arrs 按顺序），target在内循环。且内循环正序。
- （2）如果组合问题需考虑元素之间的顺序，需将 target 放在外循环，将 arrs 放在内循环，且内循环正序
1. 单词拆分
-
题目出处：139. 单词拆分
-
思路：判断一个字符串s是否能够拆分成为一个或者多个在字典wordDict中出现的单词
- ① 维护一个数组dp[i]，表示字符串i以及其之前的字串能否由wordDict中的串组成，i的范围为[0，s.len]
- ② 外层循环遍历目标字符串s，内层循环遍历字典wordDict（字典中元素可重复使用）
- ③ dp[i] = dp[i-len] || dp[i]（这里的len为字典中某个字符的长度）
public boolean wordBreak(String s, List<String> wordDict) {
int len = s.length();
boolean[] dp = new boolean[len + 1];
dp[0] = true;
for (int i = 1; i <= len; i++) {
for (String curS : wordDict) {
int size = curS.length();
if (i - size >= 0 && s.substring(i - size, i).equals(curS))
dp[i] = dp[i] || dp[i - size];
}
}
return dp[len];
}
2. 完全平方数
-
题目出处：279. 完全平方数
-
思路：将题目转换成为从数组nums[1，sqrt(n)]中，选出平方数能够组成target的组合，并且使组合中数量个数最小
- ① 维护一个dp[i]数组，i组成的结果，dp[i]表示组成结果i需要的最少数量
- ② 数组nums中的元素是可以重复使用的，所以为完全背包问题
- ③ 外层循环遍历nums取数，内层循环找不同的组合方案（从0-target中任意一个数转换到target都可以使方案+1）
- ④ 初始状态dp[0] = 0，表示结果为0的完全平方数和组合为0个，其余都为无穷大（方便取min）
- ⑤ 【dp[i] = min{dp[i]，dp[i-num*num] + 1}】
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int num = 1; num <= Math.sqrt(n); num++) {
int squareNum = num * num;
for (int i = 0; i <= n; i++) {
if (i - squareNum >= 0)
dp[i] = Math.min(dp[i], dp[i - squareNum] + 1);
}
}
return dp[n];
}
3. 组合总和
-
题目出处：377. 组合总和 Ⅳ
-
思路：nums中的数字可以重复选取，不同的顺序组成的组合是不一样的
- ① 维护数组dp[i]，表示组成和为i的组合数量
- ② 在这个题目中，由于不同的选择顺序认作不同的结果，所以我们在外层遍历dp[]数组，在内层遍历nums数组，这样的话可以表示不同的组合顺序
- ③ 【dp[i] = dp[i] + dp[i-num]】
4. 零钱兑换
-
题目出处：322. 零钱兑换
-
思路：每种硬币是无限的，需要返回能够构成指定amount额度的最小硬币数量
- ① 维护dp[i]数组，表示构成额度i所需的最少硬币数量
- ② 由于硬币可以无限使用，我们将dp[]放在外层循环，将coin放在内层循环
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, 100000); // 如果填充MAX_VALUE，可能需要考虑反转问题，所以随便找一个大数填入
dp[0] = 0; // 没有面额为0的硬币
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == 100000 ? -1 : dp[amount];
}
5. 零钱兑换2
-
题目出处：518. 零钱兑换 II
-
思路：这题和上一题不一样之处在于，在本题目中重复的组合是需要排除掉的
- ① 维护dp[i]数组，表示构成额度i的组合数量有多少
- ② 我们只需要改变一下遍历的顺序，外层循环遍历coins[]数组，内层循环遍历dp[]数组
- ③ 初始状态，dp[0] = 1，表示组成总额度为0的组合有1种（不选）
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = 1; i <= amount; i++) {
if (i - coin >= 0)
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
``
···java
网友评论