基于wordpress的英文小游戏站,外贸网站开发,网站建设制作方式有哪些,wap建站程序源码文章目录 一、279. 完全平方数二、518. 零钱兑换 II三、474. 一和零四、377. 组合总和 Ⅳ 一、279. 完全平方数
LeetCode#xff1a;279. 完全平方数 朴素想法#xff1a; 这个题目最简单的想法是#xff0c;可以用 O ( n n ) O(n\sqrt{}n) O(n n)的动态规划解决#x… 文章目录 一、279. 完全平方数二、518. 零钱兑换 II三、474. 一和零四、377. 组合总和 Ⅳ 一、279. 完全平方数
LeetCode279. 完全平方数 朴素想法 这个题目最简单的想法是可以用 O ( n n ) O(n\sqrt{}n) O(n n)的动态规划解决定义dp[i]表示整数i完全平方数的最少数量。
由于我们不太能知道都有哪些可以构成我们直接枚举 k k k且满足 k 2 i k^2i k2i找出最小的即可。
class Solution {
public:int numSquares(int n) {vectorint dp(n 1, 0x3f3f3f3f);dp[0] 0;for(int i 1; i n; i){for(int k 1; k sqrt(i); k){dp[i] min(dp[i], dp[i - k * k] 1);}}return dp[n];}
};问题抽象 这个问题是否也能转化成 完全背包问题
相当于 1 1 1~ n n n可以无限选择达到背包容量n并且使得放入的数最少。
我们可以定义 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示达到j能够选择 1 1 1~ i i i所使用的最小数字那么我们就可以像完全背包一样进行状态转移了。注意这里i最大是 n \sqrt{}n n因此时间复杂度也是 n n n\sqrt{n} nn
我们仔细看一下 可以发现实际上和方法一就是循环调个位置。
class Solution {
public:int numSquares(int n) {vectorint dp(n 1, 0x3f3f3f3f);dp[0] 0;for(int k 1; k sqrt(n); k){for(int i k * k; i n; i){dp[i] min(dp[i], dp[i - k * k] 1);}}return dp[n];}
};那么我们如何抽象问题为完全背包问题 到目前为止我们还不能直接进行问题抽象而是看到题有类似的样子才做出完全背包的想法。
我们来看看之前考虑过的问题整数拆分、322. 零钱兑换、518. 零钱兑换 II 。
他们都是 有无限个物品可以选择、这些物品组合成背包里的物品无论是体积还是质量、最后需要达成一个目标
这个目标就是我们定义的状态、 这个物品就是我们要规定什么时候能包含的、 这个背包就是总的容量
比如这个完全平方数我们要定义的状态是和为i的最少完全平方数的数量我们要规定的物品是 1 1 1~ n \sqrt{n} n 我们的最后容量就是n。
不过我们需要注意的是放入背包的物品没有顺序要求。
二、518. 零钱兑换 II
LeetCode518. 零钱兑换 II 普通的完全背包问题做到这里已经不需要优化了直接写了因为写的完全背包太多了。
完全背包问题更新 不过完全背包要注意的是从小往大来遍历因为可以选择无限个 dp[j - coins[i]]这个转移表示的是容量为j的这个背包一部分用来装一个coins[i]其余部分就是dp[j - coins[i]]的部分这个部分是可以包含coins[i]的。 我们来思考一下这个转移对不对我们来把背包具象化dp[j - coins[i]]个容量为j - coins[i]的不同背包它们都是互不相同的且都可能包含coins[i]因为coins[i]没有个数限制。然后我们把这些不同的背包都加上coins[i]这个物品这几个背包不同的 不信你拿出来看看一个一个比这一部分是至少包含一个coins[i]的可能性。而之前的dp[j]是不包含任何coins[i]的可能性。
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount 1, 0);dp[0] 1;for(int i 0; i coins.size(); i){for(int j coins[i]; j amount; j){dp[j] dp[j] dp[j - coins[i]];}}return dp[amount];}
};三、474. 一和零
LeetCode474. 一和零 这是一个0-1背包问题也就是这里每个元素只能选择一次。 这里可以定义两维来表示0和1的个数dp[i][j]表示最多有i个0和j个1的最长子集长度。
那么我们来考虑当前考虑字符串时我们提取出它的0的个数和1的个数假如分别为k和p那么就可以进行一次转移。
dp[u][i][j] max(dp[u - 1][i -k][j - p], dp[u - 1][i][j]
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorvectorint dp(strs.size() 1, vectorvectorint(m 1, vectorint(n 1, 0)));for(int i 1; i strs.size(); i){int zero_num Get(strs[i - 1]);int one_num (int) strs[i - 1].size() - zero_num;for(int j 0; j m; j){for(int k 0; k n; k){dp[i][j][k] dp[i - 1][j][k];if(j zero_num k one_num)dp[i][j][k] max(dp[i][j][k], dp[i - 1][j - zero_num][k - one_num] 1);}}}return dp[strs.size()][m][n];}
private:int Get(string s){int ans 0;for(auto ch : s){if(ch 0) ans;}return ans;}
};空间优化
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint(n 1));for(int i 1; i strs.size(); i){int zero_num Get(strs[i - 1]);int one_num (int) strs[i - 1].size() - zero_num;for(int j m; j zero_num; -- j){for(int k n; k one_num; -- k){dp[j][k] max(dp[j][k], dp[j - zero_num][k - one_num] 1);}}}return dp[m][n];}
private:int Get(string s){int ans 0;for(auto ch : s){if(ch 0) ans;}return ans;}
};我们来看看空间优化先后的状态转移的区别实际上空间优化后它直接继承了所有的前面的部分。
空间优化前很容易出错 容易写成这样
for(int j zero_num; j m; j){for(int k one_num; k n; k){dp[i][j][k] max(dp[i - 1][j][k], dp[i - 1][j - zero_num][k - one_num] 1);}
}仔细思考发现转移方程确实没错dp[i][j][k]表示考虑前i个字符串0的个数最多为j1的个数最多为k我们单独拿出来strs[i - 1]其余部分是dp[i - 1][j - zero_num][k -one_num]这一部分也是对的定义那么转移也是对的。那么问题出在哪呢
问题出在当 j z e r o _ n u m j zero\_num jzero_num和 k o n e _ n u m k one\_num kone_num时我们没有进行状态转移换句话说没有考虑当当前背包容量不能容纳strs[[i - 1]时可以放strs[0] ~ strs[i - 2]也就是说必须直接继承因为考虑前i个字符串确实有东西可以放的话 你不继承就错了。
四、377. 组合总和 Ⅳ
LeetCode377. 组合总和 Ⅳ 这里和零钱兑换II的区别在于这里的元素是有顺序的。 零钱兑换II没有顺序就像背包内放物品是没有顺序的。那么我们仅仅使用背包的思想肯定是不能得到答案的毕竟这里有放入顺序。
既然有顺序那我们枚举每一个容量的最后一个物品就能保证这几个的放法都不一样了因此可以这样进行状态转移。
也就是说我们从最小容量开始枚举它最后一个物品来保证它放的内容不一样然后依次枚举容量你会发现我们保证了每个容量的最后一个都不一样这确实能做到有顺序的问题。排列问题毕竟小容量也考虑了这些物品这些物品可以无限次放。
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorlong long dp(target 1);dp[0] 1;int mod INT_MAX;for(int i 1; i target; i){for(int j 0; j nums.size(); j){if(i nums[j])dp[i] (dp[i] dp[i - nums[j]]) % mod;;}}return dp[target];}
};题目中有一个坑的就是说答案在int范围内但是中间结果可能爆int这里有两个解决方案 1使用long long然后取模long long是为了保证中间结果的计算爆int取模是将结果映射到int范围内对于答案来说必然是没有错误的因为答案本身就在int范围内映射过后还是本身。
2对于爆int的进行摒弃原因在于答案不可能用它来转移这种背包不可能转移到其他人身上不然会产生链锁反应即使是转移了那些人也必然对答案没有贡献不然就爆int了。 for (int i 1; i target; i) {for (int num : nums) {if (num i dp[i - num] INT_MAX - dp[i]) {dp[i] dp[i - num];}}}
