当前位置：首页 > article >正文

【代码随想录day38】【C++复健】322. 零钱兑换；279.完全平方数；139.单词拆分；卡码网56. 携带矿石资源

article 2024/11/23 9:20:23

322. 零钱兑换

本来写的时候自我感觉良好，感觉这题，定能手到擒来呀，结果一写发现基本上把坑踩了一遍：

1 数组初始化

一开始初始化初始化成了0，导致最后结果不管怎样都是0；随后换成了INT_MAX，发现同样会报错，因为INT_MAX+1超范围了。一怒之下看了眼范围是从0-10000，直接设置初始值为10001，这下没问题了。

2 位置0初始化

数组初始化搞定之后，这次是忘了给0号位初始化成0。

3 忘写判断-1的条件

写出来看着返回10001，先是懵逼了一下，随后才发现，好像得判断一下什么时候返回-1，这倒是简单，直接如果是10001则返回-1即可。

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

279.完全平方数

本题倒是没遇到什么问题，直接做出来了，就是把sqrt(i)写成sqrt(n)了，看了好一会。

还有就是考虑了一下遍历顺序的问题，前面总结了排列先背包，组合先物品，但往往分不清到底是排列还是组合，比如本题是排列问题还是组合问题呢？

答案是--都不是。

class Solution {
public:
    int numSquares(int n) {
        int count = 0;
        vector<int> dp(n+1, 10001);
        dp[0] = 0;
        for(int i=0; i<=n; i++){
            for(int j=0; j<=sqrt(i); j++){
                dp[i] = min(dp[i], dp[i-j*j] + 1);
            }
        }
        return dp[n];
    }
};

139.单词拆分

本题上一周目没做过，所以算是第一次接触，结果直接毫无思路。能想到的就是这肯定是一个排列问题，因为不同的单词组成的S显然也不同。当时思考了半天怎么把一个S给拆成不同的单词才对，然后用背包去遍历这些单词，然而怎么想都感觉不对劲。

最后看了解析才想明白，每次只用根据当前位置来判断最后几个字母能不能和某个单词对得上即可，如果对得上就延续之前的true，否则直接取false即可。

随后，虽然想明白了原理，但还是在判断这块遇到了阻碍，具体来说就是这句很长的if：

if(j >= length && dp[j - length] == true && s.substr(j-length, length) == wordDict[i])

当时想了半天substr从哪里开始取，取多长，写了半天才写对，简单来说还是没搞清楚j代表什么意思。j代表背包的最后一位，所以显然是从j-length开始取length位即可。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n+1);
        dp[0] = true;
        for(int j=0; j<=n; j++){
            for(int i=0; i<wordDict.size(); i++){
                int length = wordDict[i].size();
                if(j >= length && dp[j - length] == true && s.substr(j-length, length) == wordDict[i]){
                    dp[j] = true;
                }
            }
        }
        return dp[n];
    }
};

卡码网56. 携带矿石资源

本题也是第一次接触，先看了一眼多重背包的处理方式，看到要先转摊平01背包然后再按01背包处理即可。不过虽然说起来逻辑很简单，实现起来确实蛮复杂的，尤其是ACM模式下，哪怕以咱如此扎实渣石的代码功力，也还是遇到了一点点小问题。

写了半天自信满满以为肯定能ac，结果一点运行发现越界，检查了两年半发现dp循环把j--写成j++了，真是不知道说自己什么好。属于是大风大浪都经过了，最后在一个无人在意的角落默默地似了。

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int c;
    cin >> c;
    int n;
    cin >> n;
    vector<int> weight(n);
    for(int i=0; i<n; i++){
        cin >> weight[i];
    }
    vector<int> value(n);
    for(int i=0; i<n; i++){
        cin >> value[i];
    }
    vector<int> amount(n);
    int sum = 0;
    for(int i=0; i<n; i++){
        cin >> amount[i];
        sum += amount[i];
    }
    vector<int> weightnew;
    vector<int> valuenew;
    for(int i=0; i<n; i++){
        for(int j=0; j<amount[i]; j++){
            weightnew.push_back(weight[i]);
            valuenew.push_back(value[i]);
        }
    }
    vector<int> dp(c+1);
    for(int i=0; i<sum; i++){
        for(int j=c; j>=weightnew[i]; j--){
            dp[j] = max(dp[j], dp[j-weightnew[i]]+valuenew[i]);
        }
    }
    cout << dp[c];
}

查看全文

http://www.kler.cn/a/405541.html