本文主要是介绍【随想录】Day43—第九章 动态规划part05，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
- 题目1: 1049. 最后一块石头的重量 II
- 1- 思路
- 2- 题解
- ⭐ 最后一块石头的重量 II ——题解思路
- 题目2: 494. 目标和
- 1- 思路
- 动规五部曲
- 2- 题解
- ⭐目标和 ——题解思路
- 题目3: 一和零
- 1- 思路
- 动规五部曲
- 2- 题解
- ⭐一和零 ——题解思路
题目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)
- ① 根据一维 dp 推导，
- 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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
