题目一：

322. 零钱兑换https://leetcode.cn/problems/coin-change/

思路：完全背包问题，求解最小组合数。dp[j]：凑足总额为j所需钱币的最少个数为dp[j]。同时需要确保凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;

注意：本题代码使用先遍历物品（也就是硬币），再遍历背包（amount）

代码：

class Solution {public int coinChange(int[] coins, int amount) {int n = coins.length;int[] dp = new int[amount + 1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;// 当j<coins[i]时:装不下,继承上一个dp[j]的值// 当j>=coins[i]时:可以装得下,可以选择装或者不装中价值小的(物品数小的)进行转移即:dp[j]=min(dp[j],dp[j-coins[i]+1])for (int i = 0; i < n; i++){for (int j = coins[i]; j <= amount; j++){if (dp[j - coins[i]] != Integer.MAX_VALUE)// 比较之前的dp[j]与新的也就是去掉当前coins[i]的dp[j-coins[i]]比较// +1加的是当前的coins[i]dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}// 如果没有命中则直接返回-1return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}
}

题目二：

279. 完全平方数https://leetcode.cn/problems/perfect-squares/

本题翻译：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

思路：完全背包问题，思路类似零钱兑换。还是先遍历物品（数字），再遍历背包（正整数n）。

代码：

class Solution {public int numSquares(int n) {int[] dp = new int[n + 1];// 全部初始化为最大值Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;// 遍历所有物品，必须保证≤，for (int i = 1; i * i <= n; i++) {// 后遍历背包nfor (int j = i * i; j <= n; j++){dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}return dp[n];}
}