权威的手机排行榜网站,wordpress 图片管理系统,网页设计素材,网站建设和网页设计的区别一、完全背包问题 相较于01背包#xff0c;完全背包的显著特征是每个物品可以用无数次#xff0c;遍历顺序也不需要为了保证每个物品只去一次而倒序遍历。 #includeiostream
#includevector
using namespace std;
int main(){int N,V;cinNV…一、完全背包问题 相较于01背包完全背包的显著特征是每个物品可以用无数次遍历顺序也不需要为了保证每个物品只去一次而倒序遍历。 #includeiostream
#includevector
using namespace std;
int main(){int N,V;cinNV;vectorintweight(N1,0);vectorintvalue(N1,0);for(int i0;iN;i){cinweight[i]value[i];}vectorintdp(V1,0);for(int i0;iN;i){for(int jweight[i];jV;j){dp[j]max(dp[j],dp[j-weight[i]]value[i]);}}coutdp[V]endl;return 0;
}
二、零钱兑换 一dp数组含义dp[j]为凑成j元可以的方法数 二递推公式dp[j]dp[j-coins[i]]把数组中第一个元素所能组成的方法数一直加到最后一个元素所能组成的方法数。 三初始化dp[0]1 四完全背包正向遍历背包组合问题选择先物品后背包。
class Solution {
public:int change(int amount, vectorint coins) {vectorintdp(amount1,0);//dp[j]为凑成j元的组合数dp[0]1;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){dp[j]dp[j-coins[i]];}}return dp[amount];}
};
三、组合总和Ⅳ 本题是排列问题排列问题与组合问题的区别就是遍历顺序不同 一dp数组含义dp[j]为凑成总和为j可以的方法数 二递推公式dp[j]dp[j-nums[i]]把数组中第一个元素所能组成的方法数一直加到最后一个元素所能组成的方法数。 三初始化dp[0]1 四完全背包正向遍历背包排列问题先背包后物品 class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorintdp(target1,0);dp[0]1;// for(int i0;inums.size();i){// for(int jnums[i];jtarget;j){// dp[j]dp[j-nums[i]];// }// }for(int j0;jtarget;j){for(int i0;inums.size();i){if(jnums[i]dp[j]INT_MAX-dp[j-nums[i]])dp[j]dp[j-nums[i]];}}return dp[target];}
};
四、爬楼梯 完全背包法
#includeiostream
#includevector
using namespace std;
int main(){int n,m;cinnm;vectorintpathlength;for(int i0;im;i){pathlength.push_back(i1);}vectorintdp(n1,0);dp[0]1;for(int j0;jn;j){for(int i0;im;i){if(jpathlength[i]){dp[j]dp[j-pathlength[i]];}}}coutdp[n]endl;return 0;
}
