花生壳盒子做网站服务器,桂林市人口,自助企业建站模版,建立网站做家教辅导322. 零钱兑换
看完想法#xff1a;此处是求最小值#xff0c;所以递推公式中含Min#xff0c;即dp[j] min(d[[j], dp[j - coins[i]] 1)#xff0c;初始化都为INT_MAX#xff0c;且dp[0] 0。由于不是求组合数#xff0c;所以物品和背包重量的遍历先后顺序都是可以的…322. 零钱兑换
看完想法此处是求最小值所以递推公式中含Min即dp[j] min(d[[j], dp[j - coins[i]] 1)初始化都为INT_MAX且dp[0] 0。由于不是求组合数所以物品和背包重量的遍历先后顺序都是可以的。此处要注意一个细节如果是物品for外循环背包从coins[j] 开始并且 j之前有碰到j bagweight, j--的二者的区别是j--是01背包j是完全背包背包容量优先还需要判断j - weight[i] 0,即背包有没有被装满才进行dp滚动
int coinChange(vectorint coins, int amount) {vectorint dp(amount1, amount1);dp[0] 0;//选用外部遍历物品for(int i 0; icoins.size(); i){for(int j coins[i]; j amount; j){//if需要考虑的是INT_MAX溢出的情况我们可以把max换成amount1dp[j] min(dp[j - coins[i]] 1, dp[j]);}}if (dp[amount] amount1) return -1;return dp[amount];
279.完全平方数
看完想法和零钱兑换如出一辙。dp[j]代表和为 j 的完全平方数的最少数量为 dp[j] 。初始化可以为0因为题目不要求一定找到最小数量
int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for (int i 0; i n; i) { // 遍历背包for (int j 1; j * j i; j) { // 遍历物品每次j的平方不能超过背包大小dp[i] min(dp[i - j * j] 1, dp[i]);}}return dp[n];
139.单词拆分
看完想法可以反过来想问题列表中的字符串究竟能不能把给的字符串填满。所以定义dp[j]j为字符串长度。这里因为涉及到了字符串的顺序112构成字符串121就不是原来的字符串了所以要求排列数即先遍历背包再遍历物品
bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbool dp(s.size() 1, false);dp[0] true;for (int i 1; i s.size(); i) { // 遍历背包for (int j 0; j i; j) { // 遍历物品string word s.substr(j, i - j); //substr(起始位置截取的个数)if (wordSet.find(word) ! wordSet.end() dp[j]) {//表明存在word且i的dp为truedp[i] true;}}}return dp[s.size()];
