代码随想录算法训练营day44

题目：322. 零钱兑换、279.完全平方数、139.单词拆分、多重背包

参考链接：代码随想录

322. 零钱兑换

思路：本题同样可以用完全背包问题，背包容量即为amount，物品weight和value都为硬币coins，需要求的是装满背包需要的最少物品个数。dp五部曲；dp数组，dp[j]表示装满容量为j的背包需要的最少物品个数；递推公式，这里就要详细思考一下，因为本题的dp和之前求的方法数等不一样，先装物品i，如果能先装进去，则j-coin[i]的需要最少个数为dp[j-coin[i]]，故此时dp[j]=dp[j-coin[i]]+1，由于本题求的是最少个数，故应该使用min；初始化，dp[0]为0，表示装满0最小个数为0，但由递推公式可以看出，后面的递推需要用到min，故其他dp应该全部初始化为INT_MAX，在实际代码中由于有+1操作，初始化为INT_MAX-1；遍历顺序，本题求的是最小个数，排列组合不影响，故物品容量谁先遍历都可以；举例略。时间复杂度O(n*amount)。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX-1);//后面有+1操作，确保不越界
        dp[0]=0;
        for(int i=0;i<coins.size();i++){
            for(int j=0;j<=amount;j++){
                if(coins[i]<=j){
                    dp[j]=min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        if(dp[amount]!=INT_MAX-1){
            return dp[amount];
        }
        else{
            return -1;
        }
    }
};

279.完全平方数

思路：本题即把n分解成多个完全平方数的和，也符合完全背包的模型，n即为背包容量，weight和value都为各个完全平方数[1,4,9,16…]，需要求的是最少数量，思路和上题类似。dp五部曲：dp数组，dp[j]表示j背分解为完全平方数之和的最小个数；递推公式，如果能先放进去物品i，dp[j]=min(dp[j],dp[j-nums[i]]+1)；初始化，dp[0]=0，其他初始化为最大值；遍历顺序，本题求的最小个数，遍历顺序任意；举例略。时间复杂度O(n*√n)，因为完全平方数不会超过n。

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX-1);
        dp[0]=0;
        for(int i=1;i<=int(sqrt(n));i++){//从1开始，到√n结束
            for(int j=0;j<=n;j++){
                if(i*i<=j){
                    dp[j]=min(dp[j],dp[j-i*i]+1);
                }
            }
        }
        return dp[n];
    }
};

139.单词拆分

思路：本题首先想到的是回溯法，即把s不断拆分，并判断拆分结果在不在字典中。这里需要用到记忆化递归的方式，即保存递归计算中的结果，减小时间复杂度。注意本题不需要求出每一种拆分，只需要返回bool值，故我们的backtracking可以返回bool值。回溯返回条件即拆分位置超过size，for循环即对确定start后开始拆分的位置进行循环，i从start一直到s.size()-1。如果不使用memory数组保存计算结果，则会有大量重复计算，memory数组用于保存backtracking从0~s.size()-1的计算结果，一开始全部初始化为true，一旦for循环没有返回true，则会返回true，此时修改memory数组为false，当进入backtracking时，检测memory的值，如果本来就是false，说明本个start值已经被计算过，直接返回false不用再重新计算了。时间复杂度n*O(2^n)。

class Solution {
public:
    bool backtracking(string &s,unordered_set<string> &wordSet,vector<bool> &memory,int start ){
        if(start>=s.size()){//这里写==也行
            return true;
        }
        if(!memory[start]){
            return false;//值已经被修改过，说明从start这里拆分是不可行的
        }
        for(int i=start;i<s.size();i++){
            string word=s.substr(start,i-start+1);//拆分，从start开始往后逐渐拆分
            if(wordSet.find(word)!=wordSet.end() && backtracking(s,wordSet,memory,i+1)){//如果本次拆分可以在字典中找到，且后续拆分也成功
                return true;
            }
        }
        memory[start]=false;//for循环完成，依旧没有返回true
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(),wordDict.end());//单词可以重复使用，首先第一步就是把字典去重
        vector<bool> memory(s.size(),true);
        return backtracking(s,wordSet,memory,0);
    }
};

回溯法太久没用也忘记了许多，本题让我重新回顾了一下。
然后是dp法，本题可以使用完全背包的模板，背包容量即为字符串s，物品即为s的子串。dp五部曲：dp数组，本题的dp数组和之前的背包问题都不同，dp[j]表示字符串长度为j的s子串能否由字典中的单词组成，能则为true，否则为false；递推公式，i<j，当[i,j]范围内的子串在字典中时且dp[i]为true，则dp[j]也为true，这个递推公式也是参考的背包问题的思路，相当于尾部的子串能放入背包中；初始化，dp[0]表示空串能否由字典中元素组成，但本题中s非空，故没有空串的情况，根据递推公式，dp[0]必须为true，否则后面全为false，其他值初始化为false；遍历顺序，本题的字典中单词拼成s，是有顺序可言的，故实际上是排列问题，应该先遍历s字符串，后遍历wordSet；举例略。时间复杂度O(n^3)，其中substr为O(n)复杂度。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(),wordDict.end());
        vector<bool> dp(s.size()+1,false);
        dp[0]=true;
        for(int j=1;j<=s.size();j++){//从1开始
            for(int i=0;i<j;i++){
                string word=s.substr(i,j-i);//分割子串
                if(wordSet.find(word)!=wordSet.end() && dp[i]==true){
                    dp[j]=true;
                }
            }
        }
        return dp[s.size()];
    }
};

多重背包

思路：多重背包问题，物品N，容量V，其中每个物品至多有Mi种，重量和价值都给定，求最大价值。多重背包和01背包的区别就是每个物品不止一个有给定数量，但是如果将其摊开来看，就是一个01背包问题。那么写代码的时候就是在01背包的基础上进行修改。但是我们不能直接把weight和value数组直接用新数组push_back，这样非常耗时，基本会超时。在写代码的时候需要把每种物品遍历的个数在01背包里再遍历一遍。对本题，dp五部曲：dp数组，dp[j]表示容量为j的背包能装的最大价值；递推公式，如果物品i能够先放进去，dp[j]=max(dp[j],dp[j-weight[i]]+value[i])；初始化，全部初始化为0；遍历顺序，对容量反着来；举例略。时间复杂度O(mnk)。这个基本不会考。

#include<bits/stdc++.h>
using namespace std;

int solve(int c,int n,vector<int> &weight,vector<int> &value,vector<int> &nums){
    vector<int> dp(c+1,0);
    for(int i=0;i<n;i++){
        for(int j=c;j>=0;j--){
            for(int k=1;k<=nums[i];k++){//遍历数量，对于给定的容量j和物品i，把物品的所有数量都考虑到
                if(k*weight[i]<=j){
                    dp[j]=max(dp[j],dp[j-k*weight[i]]+k*value[i]);
                }
            }
        }
    }
    return dp[c];
}

int main(){
    int c,n;
    while(cin >> c >> n){
        vector<int> weight(n,0);
        vector<int> value(n,0);
        vector<int> nums(n,0);
        for(int i=0;i<n;i++){
            cin >> weight[i];
        }
        for(int i=0;i<n;i++){
            cin >> value[i];
        }
        for(int i=0;i<n;i++){
            cin >> nums[i];
        }
        cout << solve(c,n,weight,value,nums) << endl;
    }
    return 0;
}