平台代运营_web开发技术是什么意思_东莞百度seo哪里强_广东疫情最新情况

322. 零钱兑换

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount+1,INT_MAX);dp[0]=0;for(auto& coin:coins){for(int i=1;i<=amount;i++){if(i-coin>=0&&dp[i-coin]!=INT_MAX)dp[i]=min(dp[i],dp[i-coin]+1);}}return dp[amount]==INT_MAX?-1:dp[amount];}
};

dp[i]:凑够金额i所需要的最小硬币数

转移方程：给定coin，若使用，则意味着使用之前已凑够i-coin，此时最小硬币数为：dp[i-coin]+1，遍历所有可能的coin取最小。因为每种硬币的数量是无限的，所以是完全背包问题，背包的遍历采用正序。

279. 完全平方数

class Solution {
public:int numSquares(int n) {vector<int> dp(n+1,INT_MAX);dp[0]=0;for(int i=1;i<=n;i++){//物品for(int j=1;j<=n;j++){//背包if(j-i*i>=0&&dp[j-i*i]!=INT_MAX)dp[j]=min(dp[j],dp[j-i*i]+1);}}return dp[n];}
};

dp[i]:凑够和i所需要的最小完全平方数

转移方程：给定i*i，若使用，则意味着使用之前已凑够j-i*i，此时最小硬币数为：dp[j-i*i]+1，遍历所有可能的i取最小。因为完全平方数可重复使用，所以是完全背包问题，背包的遍历采用正序。

139. 单词拆分

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

dp[i]:截止到下标i（包含i）的子串，能否被凑成。

转移方程：尝试所有可能得语料wordDict，使用双指针确认子串尾部是否可由指定word构成，如果可以，则此时dp[i]就取决于dp[i-word.length()]，只要找到一个凑成的模式，就可以提前结束内层循环。 

小细节：对字符串s加入“虚拟头”空格，并定义空格可被凑成，dp[0]=true。好处：

• 引入上述操作后，和原字符串相比，能否凑成的结果不会变化（已经定义了空格可凑成），也即，对于所求问题是等价变换。
• 初始化容易，不需要对实际的首字符写额外逻辑。
• 如果不加虚拟头，递推过程j时可能取-1的，用例： s = "leetcode", wordDict = ["leet", "code"]引入虚拟头就避免了该情况。