电脑打开做的网站总显示404,建筑防护网安全网,东莞市自然资源局官网,培训型网站建设Day44 动态规划第六天
LeetCode 322.零钱兑换
dp数组的含义#xff1a;装满容量为j的背包需要的最少物品数为dp[j] 递推公式#xff1a;dp[j]min(dp[j-coins[i]]1,dp[j]) 初始化#xff1a;dp[0]0,dp[j]INT_MAX 遍历顺序#xff1a;个数问题与遍历顺序无关#xff0c;都…Day44 动态规划第六天
LeetCode 322.零钱兑换
dp数组的含义装满容量为j的背包需要的最少物品数为dp[j] 递推公式dp[j]min(dp[j-coins[i]]1,dp[j]) 初始化dp[0]0,dp[j]INT_MAX 遍历顺序个数问题与遍历顺序无关都可以
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount1,INT_MAX);dp[0]0;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){if(dp[j-coins[i]]!INT_MAX){dp[j]min(dp[j-coins[i]]1,dp[j]);}}}if(dp[amount]INT_MAX) return -1;return dp[amount];}
};LeetCode 279.完全平方数
与零钱兑换几乎一致区别就只有物品变成了完全平方数ixi了。
class Solution {
public:int numSquares(int n) {vectorint dp(n1,INT_MAX);dp[0]0;for(int i0;in;i){for(int j1;j*ji;j){dp[i]min(dp[i-j*j]1,dp[i]);}}return dp[n];}
};LeetCode139.单词拆分
dp数组含义如果长度为i的字符串能被字典里的单词表示dp[i]true。 递推公式if([j,i]是字典里的单词 dp[j]true) dp[i]true; 初始化dp[0]truedp[i]false 遍历顺序先背包后物品从后往前
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(),wordDict.end());vectorbool dp(s.size()1,false);dp[0]true;for(int i1;is.size();i){for(int j0;ji;j){string words.substr(j,i-j);if(wordSet.find(word)!wordSet.end() dp[j]){dp[i]true;}}}return dp[s.size()];}
};强化完全背包
