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];}
};

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

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];
}