思路：零钱兑换和之前做的不同，这里的零钱兑换是一道完全背包问题，所有的零钱都可以被使用无数次，我们先定义大小为amount+1的dp数组，dp[j]表示总金额为j的最小组合的大小，dp[0]自然初始化为0.因为我们要求最小的大小，为了之后遍历的时候能顺利的更新最小值，dp数组未被初始化为特定数值的位置应当全都设置为最大的int值。
之后进行双重遍历，本题只求最小的组合大小，所以先遍历物品或者先遍历背包都是可以的，我这里习惯先遍历物品。在之前学习的基础上，很明显这里的递推公式应该为 dp[j]= Math.min(dp[j],dp[j - coins[i]]+1);整体代码如下
class Solution {
public int coinChange(int[] coins, int amount) {
// dp[j]定义为 总金额为j的最小组合的大小
int[] dp = new int[amount + 1];
// 因为要选出最小的组合，所以先默认所有位置为最大 方便覆盖
Arrays.fill(dp,Integer.MAX_VALUE);
// dp[0]初始化为即组成0的组合大小为0即不存在
dp[0] = 0;
// 先遍历物品 实际上先遍历背包也行
for (int i = 0;i < coins.length;i++){
for (int j = coins[i];j <= amount;j++){
// 当dp[j - coins[i]]有值的时候才有比较的意义
if (dp[j - coins[i]] != Integer.MAX_VALUE){
dp[j]= Math.min(dp[j],dp[j - coins[i]]+1);
}
}
}
// 当dp[amount]为最大值说明未经过修改 即达不到金额要求 返回-1 反之直接返回答案
return dp[amount] == Integer.MAX_VALUE?(-1):dp[amount];
}
}
思路：在上一道题的基础上做这道题很简单，只需要搞清楚什么是背包，什么是物品，按上一道题的思路直接进行求解即可，本题求完全平方和组成目标和的最小组合，很明显完全平方和是物品，目标和是背包大小。根据题意目标和1<=n<=10000 所以平方和的可选数值1<=i<=100,即物品是从1到100 物品价格是i*i 代入上一题的思路进行求解即可
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
// 先遍历背包 题目提示i平方小于10000 所以这里直接写死小于等于100
for (int i = 1; i <= 100; i++) {
for (int j = i*i; j <= n ; j++) {
if (dp[j - i*i]!=Integer.MAX_VALUE){
dp[j] = Math.min(dp[j],dp[j - i*i] + 1);
}
}
}
return dp[n];
}
}
