322. 零錢兌換
題目鏈接/文字講解：零錢兌換
題設(shè)：給你一個(gè)整數(shù)數(shù)組 coins ，表示不同面額的硬幣趣钱；以及一個(gè)整數(shù) amount 涌献，表示總金額。
計(jì)算并返回可以湊成總金額所需的 最少的硬幣個(gè)數(shù) 首有。如果沒有任何一種硬幣組合能組成總金額燕垃，返回 -1 。
你可以認(rèn)為每種硬幣的數(shù)量是無限的井联。
思路：動(dòng)規(guī)五部曲：
1.dp數(shù)組含義：dp[j]代表湊成j金額最少的硬幣個(gè)數(shù)卜壕。
2.遞歸表達(dá)式：湊足總額為j - coins[i]的最少個(gè)數(shù)為dp[j - coins[i]]，那么只需要加上一個(gè)錢幣coins[i]即dp[j - coins[i]] + 1就是dp[j]烙常。同時(shí)dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的轴捎，所以dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
3.初始化：dp[0]為0，其他為-1
4.遞歸順序：外物品蚕脏，里背包侦副，順序遍歷
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
for (int i = 1; i < dp.length; i++) {
dp[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < coins.length; i++) {
for (int j = coins[i]; j <= amount; j++) {
if (dp[j - coins[i]] != Integer.MAX_VALUE)dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}
279.完全平方數(shù)
題目鏈接/文字講解：完全平方數(shù)
題設(shè)：給你一個(gè)整數(shù) n ，返回 和為 n 的完全平方數(shù)的最少數(shù)量 蝗锥。
完全平方數(shù) 是一個(gè)整數(shù)跃洛，其值等于另一個(gè)整數(shù)的平方；換句話說终议，其值等于一個(gè)整數(shù)自乘的積汇竭。例如，1穴张、4细燎、9 和 16 都是完全平方數(shù)，而 3 和 11 不是皂甘。
思路：動(dòng)規(guī)五部曲：
1.dp數(shù)組含義：dp[j]代表和為n的完全平方數(shù)最少數(shù)量玻驻。
2.遞歸表達(dá)式：dp[j] = Math.min(dp[j], dp[j - square[i]] + 1)；
3.初始化：dp[0]=0;
4.遍歷順序：外物品，里背包璧瞬，順序遍歷户辫。
class Solution {
public int numSquares(int n) {
int[] square = new int[101];
for (int i = 0; i < square.length; i++) {
square[i] = i * i;
}
int[] dp = new int[n + 1];
int max = Integer.MAX_VALUE;
for (int i = 1; i < dp.length; i++) {
dp[i] = max;
}
dp[0] = 0;
for (int i = 1; i < square.length; i++) {
for (int j = square[i]; j <= n; j++) {
if (dp[j - square[i]] != max) dp[j] = Math.min(dp[j], dp[j - square[i]] + 1);
}
}
return dp[n];
}
}
