算法训练营第四十八天 | 卡码网57 爬楼梯、LeetCode 322 零钱兑换、LeetCode 279 完全平方数
卡码网57 爬楼梯
排列dp + 完全背包问题
代码如下：
import java.util.*;public class Main {public static void main(String[] args) {int n, m;Scanner in = new Scanner(System.in);n = in.nextInt();m = in.nextInt();int[] dp = new int [n + 1];dp[0] = 1;for (int j = 0; j <= n; j++) {for (int i = 1; i <= m; i++) {if (j >= i) {dp[j] += dp[j - i];}}}System.out.println(dp[n]);}
}LeetCode 322 零钱兑换
这题dp数组含义和完全背包其实是完全相反的，要求能组成所要求总金额的最小钱币数。但是递推公式和完全背包问题几乎是完全一样了。只不过要注意初始化时候除dp[0]之外不能初始化为0，否则按照递推逻辑就会全部是0了。我们可以采取将dp[i]初始化为i+1的形式，最后如果还是等于i+1说明没有硬币组合满足条件，直接返回-1即可。
递推逻辑中也要判断dp[j-coins[i]]是否等于j-coins[i]+1看递推中的子问题是否已经有解。
代码如下：
class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];for (int i = 1; i <= amount; i++) dp[i] = i + 1;for (int i = 0; i < coins.length; i++) {for (int j = 0; j <= amount; j++) {if (j >= coins[i] && dp[j - coins[i]] != j - coins[i] + 1)dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}if (dp[amount] == amount + 1) return -1;return dp[amount];}
}LeetCode 279 完全平方数
在上面两题理解了的基础上很容易想出来。
代码如下：
class Solution {public int numSquares(int n) {int x = (int)Math.sqrt(n);int[] dp = new int[n + 1];for (int i = 1; i <= n; i++) dp[i] = i + 1;for (int i = 1; i <= x; i++) {for (int j = 0; j <= n; j++) {if (j >= i * i && dp[j - i * i] != j - i * i + 1) {dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}}return dp[n];}
}