学校网站建设与管理办法,苏州高端网站建设机构,想建立一个网站,专注建设高端网站文章目录前言动态规划的维度二维动规leetcode416、分割等和子集leetcode1049. 最后一块石头的重量 IIleetcode494、目标和三维动规leetcode474. 一和零结语前言
大家好久不见#xff0c;这次我们一起来学习一下动态规划中怎么确定维度#xff0c;和对应问题如何解决。
动态…
文章目录前言动态规划的维度二维动规leetcode416、分割等和子集leetcode1049. 最后一块石头的重量 IIleetcode494、目标和三维动规leetcode474. 一和零结语前言
大家好久不见这次我们一起来学习一下动态规划中怎么确定维度和对应问题如何解决。
动态规划的维度
一个维度只有物品 两个维度物品和容量 三个维度物品和容量1和容量2
之前讲解动态规划问题时斐波那契数列就是一个很简单的一维动态规划问题因为我们要考虑的状态只有这个数的值一维动态规划之后讲解了01背包问题也就是有了第二个维度不仅要考虑物品还要考虑背包容量二维动态规划
其实在这里一定要明确好状态到底是什么在我看来与要求结果相关的状态都是可以列为维度的我们是将物品范围和背包容量都列为了状态因为他们都会影响结果 二维动规
leetcode416、分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 示例 1 输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。示例 2 输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。 这个问题要我们寻找等和的子集我们可以把nums数组里的元素抽象为背包问题里的石头把分成的两个等和子集抽象为背包。 dp[i][j] 表示前i个元素放到容量为j的背包的最大重量 dp[i][j] max(dp[i-1][j],dp[i-1][j-nums[i]]nums[i])
就算压缩为一维动态规划那也是压缩的空间而已本质上我们还是定义了两个状态
#define MAX(a,b) ((a)(b)?(a):(b))bool canPartition(int* nums, int numsSize){int sum 0;for(int i 0;inumsSize;i){sumnums[i];}if(sum%2 ! 0) return false;int target sum / 2;int* dp (int*)calloc(sizeof(int),target1);//先遍历物品再遍历列for(int i 0;inumsSize;i){for(int j target;jnums[i];j--){dp[j] MAX(dp[j],dp[j-nums[i]]nums[i]);}} if(dp[target] target) return true;return false;
}leetcode1049. 最后一块石头的重量 II
有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下
如果 x y那么两块石头都会被完全粉碎 如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。 最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。 示例 1 输入stones [2,7,4,1,8,1] 输出1 解释 组合 2 和 4得到 2所以数组转化为 [2,7,1,8,1] 组合 7 和 8得到 1所以数组转化为 [2,1,1,1] 组合 2 和 1得到 1所以数组转化为 [1,1,1] 组合 1 和 1得到 0所以数组转化为 [1]这就是最优值。 这道题目我们要获得撞后剩下的最小质量只需要将这堆石头尽可能分为两堆一样重量的石头相互碰撞即可。 在这道题目里nums数组里的元素是石块总重量的一半即是背包容量我们要尽可能填满这一半的石头。
dp[i][j] ——前i个石块放入j的背包的最大重量。dp[i][j] max(dp[i-1][j],dp[i-1][j-nums[i]]nums[i])
优化思路也和01背包问题一样即滚动数组压缩
参考代码
#define MAX(a,b) ((a)(b)?(a):(b))
int lastStoneWeightII(int* stones, int stonesSize){int sum 0;for(int i 0;istonesSize;i){sum stones[i];}int target sum/2;int dp[1501] {0};for(int i 0;istonesSize;i)//遍历物品{for(int j target;jstones[i];j--){dp[j] MAX(dp[j],dp[j-stones[i]]stones[i]);}}return sum - dp[target] - dp[target];
}leetcode494、目标和
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘’ 或 ‘-’ 然后串联起所有整数可以构造一个 表达式
例如nums [2, 1] 可以在 2 之前添加 ‘’ 在 1 之前添加 ‘-’ 然后串联起来得到表达式 “2-1” 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 示例 1 输入nums [1,1,1,1,1], target 3 输出5 解释一共有 5 种方法让最终目标和为 3 。 -1 1 1 1 1 3 1 - 1 1 1 1 3 1 1 - 1 1 1 3 1 1 1 - 1 1 3 1 1 1 1 - 1 3 这道问题其实也是要我们分为两组本质上nums数组里的元素就是石块分组的大小仍然是背包大小。唯一不同的是我们dp数组在定义上变成了要求多少种方法
dp[i][j] ——前i个元素放入容量为j的背包有多少种方法dp[i][j] dp[i-1][j] dp[i-1][j-nums[i]]; //可以放也可以不放两者加起来就是总方法数
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {//分组背包问题,一组放一组放-凑成targetint sum 0;for(auto e : nums){sume;}//left rightif(abs(target) sum) return 0;if((target sum)%2 1) return 0;int left (target sum)/2;vectorint dp(left1,0);dp[0] 1;for(int i 0;inums.size();i){for(int j left;jnums[i];j--){dp[j] dp[j-nums[i]];}}return dp[left];}
};三维动规
leetcode474. 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素集合 x 是集合 y 的 子集 。 示例 1 输入strs [“10”, “0001”, “111001”, “1”, “0”], m 5, n 3 输出4 解释最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} 因此答案是 4 。 其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意因为它含 4 个 1 大于 n 的值 3 。 说白话就是用j个0和k个1最多能凑成几个nums中的字符串
这道题可以将数组里的元素抽象为石头0和1的数量抽象为背包容量很显然现在有两个背包容量
dp[i][j][k]——在前 i 个字符串中使用 j 个 0 和 k 个 1的情况下最多可以得到的字符串数量。dp[i][j][k] max(dp[i-1][j][k],dp[i-1][j-num1][k-num0] 1); 其实就是要不要把这个字符串放进来比一下大的就行
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint (n 1, 0)); // 默认初始化0//dp[i][j] 表示容量为ij的背包能装的最大重量for(string str : strs){int onenum 0,zeronum 0;for(char c : str){if(c 1)onenum;elsezeronum;}for(int i m;izeronum;i--){for(int j n;jonenum;j--){dp[i][j] max(dp[i][j],dp[i-zeronum][j-onenum]1);}}}return dp[m][n];}
};结语
到这里本篇文章就结束了希望能对你学习动态规划有所帮助我们下次见~
