leetcode刷题详解九

/**一维数组的写法，但是我感觉不好理解**/
int coinChange(vector<int>& coins, int amount) {
    //dp[i]表示凑成总金额为i所需要的最小硬币个数
    vector<int> dp(amount+1,amount+1);
    dp[0] = 0;
    int n = coins.size();
    for(int i = 0; i < n; i++){
        for(int j = 1; j < amount + 1; j++){
            if(j - coins[i] >= 0){
                dp[j] = min(dp[j],dp[j - coins[i]]+1);
            }
        }
    }
    //处理凑不出来amount的情况
    if(dp[amount] == amount+1){
        return -1;
    }
    return dp[amount];
}

/*二维数组*/
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int len = coins.size();
        vector<vector<int>> dp(len+1, vector<int>(amount+1, 10001));
        for(int i = 0; i < len + 1; i++){
            dp[i][0] = 0;
        }
        for(int i = 1; i< len+1; i++){
            for(int j = 0;j < amount+1; j++){
                if(j - coins[i-1] >= 0){
                    //这句话才是完全背包和01背包的不同，和精髓
                    //不是i-1是因为完全背包的数可以重复取
                    dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i-1]] + 1);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        for(int i = 1; i < len + 1; i++){
            for(int j = 0;j < amount+1;j++){
                cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        }
        
        return dp[len][amount] == 10001?-1:dp[len][amount];
    }
};

这道题的主要难点在于如何判断有些凑不到amount的情况。由于这道题动态规划求最小，我们就初始化dp数组最大，大于amount就可以了。那么如果dp[amount] = 初始化的那个值，说明我们凑不到 返回-1

int change(int amount, vector<int>& coins) {
    int n = coins.size();
    //dp[i][j]表示用前i个硬币凑齐j所需要的个数
    vector<vector<int>> dp(n+1, vector<int>(amount+1, 0));
    dp[0][0]  = 1;
    for(int i = 1; i < n + 1; i++){
        for(int j = 0; j < amount + 1; j++){
            if(j - coins[i -1] < 0){
                dp[i][j] = dp[i - 1][j];
            }else{
                dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i-1]];
            }
        }
    }
    return dp[n][amount];
}
/******二维数组会超时，但又不超时了 吐了！！！*****/
int change(int amount, vector<int>& coins) {
    int len = coins.size();
    vector<vector<int>> dp(len+1, vector<int>(amount+1, 0));
    dp[0][0] = 1;
    for(int i = 1; i < len + 1; i++){
        for(int j = 0; j < amount+1; j++){
            if(j-coins[i-1] >= 0){
                dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j]; 
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[len][amount];
}

• 思路

  比如说amount = 5, coins = [1, 2, 5]，有4种方式可以凑成：

  5=5
  5=2+2+1
  5=2+1+1+1
  5=1+1+1+1+1
  

  观察这几种情况可以发现为啥用动态规划，比如5=2+2+1，那么组成2有多少种就可以查dp数组了，所以要用动态规划。

  对于这道题其实关键点有两个

  1. $dp[0][0]=1$;当没硬币凑出0的情况为1，这个切记
  2. 第二个就是状态转移方程了。这道题问的是几种可能，因此只要是满足凑出j的都要加上才行（好好理解这句话）。

这道题其实是组合数，至于为啥是组合数，一定要结合377题来看。因为377题是有顺序要求的，因此事排列数

这道题暗含了一个数学定理即四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。 推论：满足四数平方和定理的数n（四个整数的情况），必定满足 n=4^a

int numSquares(int n) {
        int upper_bound = (int)sqrt(n);
        //记住！求最少的，dp数组一定要设置为最大！
        vector<int> dp(n + 1, n + 1);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 1; i < n + 1; i++){
            for(int j = 1; j < upper_bound + 1; j++){
                if(i - pow(j, 2) < 0){
                    dp[i] = dp[i];
                }else{
                    dp[i] = min(dp[i],dp[i - pow(j, 2)] + 1);
                }
            }
        }
        return dp[n];
    }

做到这里回头再看背包问题的基本模板会发现一切都是那么简单，记住背包问题的模板！

• 注意的问题

  这道题中我们可以总结出一些问题，即求最小值时初始化dp数组一定要最大才行，不能初始化0了

这道题有两个点。

1. 对于c++中判断某个字符串是否在另一个数组中，就是用这种容器存储，然后容器.find(str) != 容器.end()表明找到了，其他时候表明找不到。
2. 对于子串的问题，和普通的背包问题是不一样的。普通的背包问题我们外层遍历容量，内层遍历物品之类的。但是对于字符串，特别是这道题，抽象成背包问题时候，循环就要稍微变一下了。对于字符串问题，我们一定要遍历某一字符串的子串才行。比如说这道dp[i]表示前i个字符串是否能由字典中单词组成，这个时候我们不能遍历字典了，要遍历这前i个字符串的子串!切记，这是重点中的重点！

set<string> wordDict_set;
		//好像vector也能判断，不用set	
        for(auto str : wordDict){
            wordDict_set.insert(str);
        }
        //表示前n个单词是否可以表示出来
        int n = s.size();
        int m = wordDict.size();
        vector<bool> dp(n+1, false);
        dp[0] = true;
        for(int i = 1 ; i < n + 1; i++){
            for(int j = 0; j < i ; j ++){
                string temp = s.substr(j,i-j);
                if(dp[j] && wordDict_set.find(temp) != wordDict_set.end()){
                    dp[i] = true;
                }
            }
        }
        return dp[n];
    }

看到这道题的第一反应是所有奇数索引和偶数索引相加然后比较大小，但是仔细一想发现不太对。因为比如说：[3,2,4,9]这个数组最大值是3+9，所以跟奇偶没有任何关系

int rob(vector<int>& nums) {
       int n = nums.size();
       vector<int> dp(n+1, 0);
       dp[1] = nums[0];
       for(int i = 2; i < n + 1; i++){
           dp[i] = max(dp[i - 1], dp[i - 2]+nums[i - 1]);
       }
       return dp[n];
    }

• 总结一下

  这道题还是比较简单的，中规中矩

还是照例分析一下思路吧。

这道题和上一道题的唯一区别就在于首尾也是相连的，仅此而已！

这就表明①如果我们选择了首家偷，就不能偷最后一家。②如果偷第二家，可以考虑最后一家。

因此我们可以把这个数组拆分成两种情况求最大值

每个数组当做打家劫舍1来做

int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1){
            return nums[0];
        }
        if(n == 2){
            return nums[0] > nums[1] ? nums[0] : nums[1];
        }
        vector<int> nums_temp1(n-1);
        vector<int> nums_temp2(n-1);
        for(int i = 0; i < n - 1; i++){
            nums_temp1[i] = nums[i + 1];
        }
        for(int i = 0; i < n - 1; i++){
            nums_temp2[i] = nums[i];
        }
        int nums_temp1_rob = rob_with_nums(nums_temp1);
        int nums_temp2_rob = rob_with_nums(nums_temp2);
        return nums_temp1_rob > nums_temp2_rob ? nums_temp1_rob : nums_temp2_rob;
    }
    int rob_with_nums(vector<int>& nums_temp){
        int n = nums_temp.size();
        vector<int> dp(n+1, 0);
        dp[1] = nums_temp[0];
        for(int i = 2; i < n + 1; i++){
            dp[i] = max(dp[i - 1], dp[i - 2] + nums_temp[i -1]);
        }
        return dp[n];
    }

严格来说这是一道二叉树的题

就只有两种情况呗，①偷根节点，②不偷根节点

其实代码很好写，但是会报超时错误！

下面来找一下原因：我们计算每个节点对应的最高金额，因此这里面也可以记忆化搜索，即父亲节点的最大金额其实不用再去重新算了，因为子节点的最大金额可以存起来，要是用的话直接用就好，这样可以节省很多时间。因此我们需要用一个key-value来存储每个节点对应的最大金额

map<TreeNode*, int> temp;
    int rob(TreeNode* root){
        if(!root){
            return 0;
        }
        if(root->left == nullptr && root->right == nullptr){
            return root->val;
        }
        if(temp.find(root) != temp.end()){
            return temp[root];
        }
        int cash1 = root->val;
        int cash2 = 0;
        if(root->left != nullptr){
            cash1 += rob(root->left->left) + rob(root->left->right);
        }
        if(root->right != nullptr){
            cash1 += rob(root->right->left) + rob(root->right->right);
        }
        cash2 += rob(root->left) + rob(root->right);
        int max_rob = max(cash1, cash2);
        temp[root] = max_rob;
        return max_rob;
    }

这又是一类动态规划题型，核心思路是对于数组$dp[i][j]$中的j只有0和1两种，表示卖或者不卖

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> dp(n+1, vector<int>(2, 0));
    //具体细节，第一次情况要特别说明
    //循环从第二天开始
    dp[1][0] = 0; 
    dp[1][1] = -prices[0];
    for(int i = 2; i < n + 1; i++){
        dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i-1]);
        //1表示有，有可能上一次的那个还没卖，或者重新买了(-prices)
        dp[i][1] = max(dp[i-1][1], -prices[i-1]);
    }
    return dp[n][0];
}
//************贪心算法**************/
int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int max_profit = 0;
    int min_price = prices[0];
    for(int i = 0; i < n; i++){
        min_price = min(prices[i], min_price);
        max_profit = max(max_profit, prices[i] - min_price);
    }
    return max_profit;
}

int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n+1,vector<int>(2, 0));
        dp[1][0] = 0;
        dp[1][1] = -prices[0];
        for(int i = 2; i < n + 1; i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1]);
        }
        return dp[n][0];
    }

总结一下：这道题和121题的区别在于这道题不限制交易的次数，因此可以无数次交易而不是1次

所以代码的区别主要在于如果这次买了，那么状态转移就是上一次就买了，或者上一次卖掉了$dp[i-1][0]$然后再买

只能一笔交易和不限制交易次数的情况比较好写，因为状态转移很简单，但是当多次的话，就要用三元组了

int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(3, vector<int>(2, 0)));
        for(int k = 0; k < 3; k++){
            dp[1][k][0] = 0;
            dp[1][k][1] = -prices[0];
        } 
        for(int i = 2; i < n + 1; i++){
            for(int k = 1; k < 3; k++){
                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i-1]);
                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i-1]);
            }
        }
        return dp[n][2][0];
    }

• 注意事项

  1. 2次的话影响不能消除，必须用三元组写

  2. dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i-1]);

     这行代码中，因为我们求得是1即买入了，那么上次没买这次买了，这次买了k就要减一