【随想录】Day43—第九章 动态规划part05

本文主要是介绍【随想录】Day43—第九章 动态规划part05，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

题目1: 1049. 最后一块石头的重量 II

• 题目链接：1049. 最后一块石头的重量 II

---

1- 思路

思路：尽量将石头分为重量相似的两堆，例如 [2,7,4,1,8,1] sum = 23 分为 sum/2 = 11

• 分为重量相等的两堆也就是 11 和 12 ，让这两堆相撞结果为 1
• 问题化简 ——> 化简为 如何将重量划分为 容量 11 的石头堆
• 该问题就和 划分 等和 子集很像

动规五部曲

• 1. 定义 dp 数组以及其含义
  • 本题中，容量实际上就是为石头的价值。即装满容量为 11 的背包的最大价值就是 装满容量为 11 的背包的最大重量 ——> 所求为 装满容量 11 背包的最大重量
  • 类似于 等和数组 均分的思路
• 2. 递推公式
  • dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
• 3. dp 数组初始化
  • dp[0] = 0
• 4.确定遍历顺序
  • ① 先遍历重量：for(int i = 0 ; i < n;i++)
  • ② 再遍历背包：for(int j = target; j >= stones[i];j--)

---

2- 题解

⭐ 最后一块石头的重量 II ——题解思路

class Solution {public int lastStoneWeightII(int[] stones) {// 定义 dp 数组// dp 数组含义，为 j 容量的最大收益int sum = 0;for(int i : stones){sum+=i;}int target = sum/2;int n = stones.length;int[] dp = new int[target+1];// 2. 递推公式 dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);// 3. 初始化dp[0] = 0;// 4. 遍历顺序// i 从 0 遍历到 n// j 从 target 遍历到 weight[i]for(int i = 0 ; i < n;i++){for(int j = target; j >= stones[i];j--){dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);}}return sum - 2*dp[target];}
}

---

题目2: 494. 目标和

• 题目链接：494. 目标和

---

1- 思路

思路：将集合分为 加法集合 left ，减法集合 right
推导过程：

• 定义 ①sum = left + right
• 同时 ②left - right = target
• 由 ① 得到 ③ right = sum - left
• 将 ③ 带入 ② 得到 left = (target + sum)/2

实际求解

• 根据 left = (target + sum)/2 ——> 寻找能组合成 left 的种类数

举例：
此时对于样例[1,1,1,1,1] ，只需要求出正数和为 4 的情况种类，其他就是负数集合
遇到 left 不能整除的情况：则没有这种情况，凑不出 target ——> 直接return 0
求解目标：

• 给你一个容量为 left 的背包，有多少种情况 可以将该背包装满？

动规五部曲

• 1. 定义 dp 数组即 dp 数组含义
  • dp[j] 代表装满容量为 j 的背包，拥有的 dp[j] 种方法，也就是考虑正数 left 的方法数
• 2. 递推公式
  • 此时的递推公式类似于爬楼梯
  • 如果已经有 物品 重量1 ，则需要 dp[4] 种方法 凑出 dp[5]
  • 如果已经有 物品 重量2 ，则需要 dp[3] 种方法 凑出 dp[5]
  • 如果推导 dp[5] = dp[4] + dp[3] + dp[2] + dp[1] +dp[0]
  • 最终：dp[j] += dp[j - numbers[i]]
• 3. dp 数组初始化
  • 理解 [0] ，target = 0 ，此时 left = (target + sum)/2 ，left 为 0 ，则正数集合为 0 有一种情况 也就是取 +
• 4. 确定遍历顺序
  • ① 先遍历重量：for(int i = 0 ; i < n;i++)
  • ② 再遍历背包：for(int j = left; j >= weight[i];j--)

---

2- 题解

⭐目标和 ——题解思路

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int i:nums){sum += i;}//如果target的绝对值大于sum，那么是没有方案的if (Math.abs(target) > sum) return 0;if((target+sum)%2 != 0){return 0;}int left = (target+sum)/2;// 1. 定义 dp 数组int[] dp = new int[left+1];// 2. 确定递推公式// dp[j] += dp[j-weight[i]]// 3. 初始化dp[0] = 1;// 4. 确定遍历顺序for(int i = 0 ; i < nums.length;i++){for(int j = left;j>=nums[i];j--){dp[j] += dp[j-nums[i]];}}return dp[left];}
}

---

题目3: 一和零

• 题目链接：474. 一和零

---

1- 思路

本题目标

• 装满这个背包 ，最多有多少种物品？

动规五部曲

• 1. 确定 dp 数组含义
  • dp[m][n] ，装满 m 个 0 和 n 个 1 的背包，最多的物品数
• 2. 确定递推公式
  • ① 根据一维 dp 推导， dp[j] = Math.max(dp[j],dp[j-weight[i]) + value[i]
  • 本题物品的重量是 x 个 0 和 y 个 1，背包的重量相当于 m 个 0 和 n 个 1
  • 根据 ① 推导dp[i][j] = Math.max(dp[i][j] , dp[i-x][j-y]+1)
• 3. dp 数组初始化
  • dp[0][0] = 0
• 4. 遍历顺序
  • 先遍历字符串数组
  • 将每个遍历到的字符串的 x 个 0 和 y 个 1 取出来

---

2- 题解

⭐一和零 ——题解思路

class Solution {public int findMaxForm(String[] strs, int m, int n) {// 1. 定义 dp 数组// 包含 i个0 j个1 的自己的最大长度int[][] dp = new int[m+1][n+1];// 2. 确定递推公式// dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);// 3. dp 数组初始化dp[0][0] = 0;// 4. 确定遍历顺序for (String str : strs){int x = 0;int y = 0;for(char c:str.toCharArray()){if(c == '0'){x++;}else{y++;}}// 反向遍历for(int i = m;i>=x;i--){for(int j = n ; j>= y;j--){dp[i][j] = Math.max(dp[i][j],dp[i-x][j-y]+1);}}}return dp[m][n];}
}

这篇关于【随想录】Day43—第九章 动态规划part05的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---