3.3 log | 474.一和零，518.零钱兑换II，377. 组合总和 Ⅳ,322. 零钱兑换

474.一和零

class Solution {
public:
    int findMaxForm(vector& strs, int m, int n) {
        vectorint>> dp(m+1,vector<int>(n+1,0));
        for(string str:strs){
            int zeroNum=0;
            int oneNum=0;
            for(char c:str){
                if(c=='0') zeroNum++;
                else oneNum++;
            }
            for(int i=m;i>=zeroNum;i--){
                for(int j=n;j>=oneNum;j--){
                    dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }
        }
        return dp[m][n];
    }
};

这道题也能转化为01背包问题，以往题目，物品包括重量，价值两个属性，背包包括容积一个属性，以前题目，容积以及重量都是一维的，而这道题，物品的重量为x，y两个维度，价值是1，添加一个加一，背包的容积也变为x，y两个维度，所以dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1),数组初始化是，dp[0][0]=0,在创建数组的时候已经初始化了，故可以省略

518.零钱兑换II

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1,0);
        dp[0]=1;
        for(int i=0;isize();i++){
            for(int j=0;j<=amount;j++){
                if(j>=coins[i]) dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

这道题和前面目标和类似，和爬台阶类似，都是求最多有多少种方法，所以dp[j]+=dp[j-nums[i]]，遍历顺序涉及到组合问题和排列问题，这道题就是求能装amount最多有多少方法，不涉及排列，所以是组合问题，所以是先遍历物品再遍历背包，不能交换遍历顺序

377. 组合总和 Ⅳ

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1,0);
        dp[0]=1;
        for(int j=0;j<=target;j++){
            for(int i=0;isize();i++){
                if(j>=nums[i]&&dp[j]
            }
        }
        return dp[target];
    }
};

这道就是典型的排列问题，区分元素的先后顺序，所以先遍历背包再遍历物品，确保每个背包都能遍历到所有物品，有一点需要注意的就是，dp[j]+dp[j-nums[i]]有可能大于INT_MAX，需要添加限制条件，dp[j]

322. 零钱兑换

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,amount+1);
        dp[0]=0;
        for(int i=0;isize();i++){
            for(int j=0;j<=amount;j++){
                if(j>=coins[i]) dp[j]= min(dp[j],dp[j-coins[i]]+1);
            }
        }
        if(dp[amount]==amount+1) return -1;
        return dp[amount];
    }
};

本题有几个值得注意的地方，这是求装背包所用最少硬币的数量，因为是求数量不是求方法，所以不在乎是排列还是组合，所以两层for循环的顺序可以交换，初始化dp[0]=0，容量0放不下任何东西，因为是求最少硬币，所以初始化dp数组其他元素不能为0，否则，dp数组都全取最小值为0了，所以初始化其他元素为amout+1，所以递推公式为dp[j]=min(dp[j],dp[j-coin[i]]+1)