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"]引入虚拟头就避免了该情况。