*322. 零钱兑换

leetcode题目地址

dp[j]存储amount为j时所需要的最少硬币数。当j为0时需要0个硬币，因此dp[0]赋值为0.

因为是取最少硬币数，因此初始化需要赋值一个最大值。

状态转移方程：dp[j] = min(dp[j], dp[j-coins[i]]+1)

本题是求最少的硬币个数，因此排列组合都无所谓，不会影响结果（因为每次更新是取min），所以遍历顺序背包和硬币可以互换。

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

// java
class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];for(int i=1; i<=amount; i++) dp[i] = amount+1;dp[0] = 0;for(int i=0; i<coins.length; i++){for(int j=coins[i]; j<=amount; j++){if(dp[j-coins[i]]>=0)dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);}}return dp[amount]==amount+1?-1:dp[amount];}
}

*279. 完全平方数

leetcode题目地址

完全背包。

dp[j]的意义：存储j可以最少由dp[j]个完全平方数之和组成。

同上题思路差不多，这里需要注意初始化的问题，dp[0]赋值为0，其余元素初始化一个最大值。

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

// java
class Solution {public int numSquares(int n) {int[] dp = new int[n+1];for(int i=0; i<=n; i++) dp[i] = n+1;dp[0] = 0;for(int i=1; i<=n; i++){for(int j=i*i; j<=n; j++){dp[j] = Math.min(dp[j], dp[j-i*i]+1);}}return dp[n];}
}

*139. 单词拆分

leetcode题目地址

本题较难以理解，对于字符串匹配如何转换成背包问题且用dp数组保存结果是一个难点。

dp[j]存储的是字符串s中长度为j的子串是否在wordDict中可以匹配。

在更新dp[j]时，只有前面的子串匹配成功了才会更新后面匹配成功的子串，也就是当访问到子串s[i-j]时，i<j，dp[i]==true时才更新dp[j]。

dp[0]初始化为true，没有实际含义（可以理解为空串），其他位置均为false。

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

// java
class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp = new boolean[s.length()+1];dp[0] = true;for(int j=1; j<=s.length(); j++){for(int i=0; i<j; i++){if(wordDict.contains(s.substring(i, j)) && dp[i]){dp[j] = true;}}}return dp[s.length()];}
}