nodejs和wordpress,福建seo快速排名优化,小程序开发教程免费,合肥做核酸最新通知10背包#xff1a; 二维内侧与外侧都是正序遍历#xff0c;二维的内侧与外侧是背包还是物品无所谓#xff1b;
10背包#xff1a; 一维外侧是正序#xff0c;内侧是倒序#xff1b; 目的是为了一个物品只选取一次#xff1b;一维内侧一定要是背包#xff1b;原因我想了…10背包 二维内侧与外侧都是正序遍历二维的内侧与外侧是背包还是物品无所谓
10背包 一维外侧是正序内侧是倒序 目的是为了一个物品只选取一次一维内侧一定要是背包原因我想了下还是因为这个内侧是倒序的原因导致的。因为本来每个dp【j】的状态都取决于他之前dp[j-n]的状态, 然后你还是从最后面开始往前算的那必须先把row的数据算出来不然下面一行的数据用不了前面的数据了
完全背包 一维外侧和内侧都是正序遍历然后内侧外侧也都无所谓 我分析了一下感觉还是和10背包二维的是一个原因因为左边的数据已经算出来了而且你还是正序 518.零钱兑换II
自己能写出来一些细节还是不对这个题是求组合所以是没有顺序这么一说的内侧外侧就不能交换顺序了具体理由以及总结如下自己写运气好刚好写对了 class Solution {
public:int change(int amount, vectorint coins) {vectorint dp( amount 1, 0);int sum 0;//for ( int i 0; i coins.size(); i) {// sum coins[i];//}这个题由于可以重复选取所以这里不能这么写//if (sum amount) return 0;dp[0] 1; //由于是顺序遍历的后面的数据依靠前面的所以这个只能定0但是实际没啥含义for ( int i 0; i coins.size(); i) {for (int j coins[i]; j amount; j) {dp[j] dp[j - coins[i]];}}return dp[amount];}
}; 先遍历物品后遍历背包是这样比如外层循环固定coins【1】在内层循环遍历背包时随着背包不断增加coins【1】可以重复被添加进来而由于外层循环固定了因此coins【2】只能在下一次外层循环添加进不同大小的背包中这么看的话coins【i1】只能在coins【i】之后了如果先遍历背包后遍历物品那么外层循环先固定背包大小j然后在大小为j的背包中循环遍历添加物品然后在下次外层循环背包大小变为j1此时仍要执行内层循环遍历添加物品也就会出现在上一轮外层循环中添加coins【2】的基础上还能再添加coins【1】的情况那么就有了coins【1】在coins【2】之后的情况了。 377. 组合总和 Ⅳ
这道题和前面那道题一样就是改成了要写排列的代码这个要记一下其他的和上面那个题一样。
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(target 1, 0);dp[0] 1;for (int i 0; i target; i) {for ( int j 0; j nums.size(); j) {if (i - nums[j] 0 dp[i] INT_MAX - dp[i - nums[j]]) dp[i] dp[i - nums[j]]; }} //求排列先遍历背包return dp[target];}
};
