代码随想录 Day45 - 动态规划（七）
作者：jjn0703
- 2023-08-20 江苏
本文字数：1371 字
阅读完需：约 4 分钟
70. 爬楼梯
使用完全背包的思想，重新实现爬楼梯的题目。每一次可选的步数设置为完全背包的选项。
package jjn.carl.dp;
import java.util.Scanner;
/** * @author Jiang Jining * @since 2023-08-20 23:11 */public class LeetCode70_ClimbStairs { public int climbStairs(int n) { int[] dp = new int[n + 1]; dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= 2; j++) { if (i >= j) { dp[i] += dp[i - j]; } } } return dp[n]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int stairs = new LeetCode70_ClimbStairs().climbStairs(n); System.out.println(stairs); }}
复制代码
322. 零钱兑换
dp 数组不能初始化为 Integer.MAX_VALUE，因为有+1 的操作，可能在某些 case 上就越界了。
package jjn.carl.dp;
import java.util.Arrays;import java.util.Scanner;
/** * @author Jiang Jining * @since 2023-08-20 23:33 */public class LeetCode322 { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, 10001); dp[0] = 0; for (int i = 0; i <= amount; i++) { for (int j = 0; j < coins.length; j++) { if (i >= coins[j]) { dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); } } } return dp[amount] == 10001 ? -1 : dp[amount]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int coinNum = scanner.nextInt(); int amount = scanner.nextInt(); int[] coins = new int[coinNum]; for (int i = 0; i < coinNum; i++) { coins[i] = scanner.nextInt(); } int coinChange = new LeetCode322().coinChange(coins, amount); System.out.println(coinChange); }}
复制代码
279. 完全平方数
完全背包的运用题目。
package jjn.carl.dp;
import java.util.Arrays;import java.util.Scanner;
/** * @author Jiang Jining * @since 2023-08-20 22:59 */public class LeetCode279 { public int numSquares(int n) { int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; int max = (int) Math.sqrt(n); for (int i = 1; i <= max; i++) { for (int j = i * i; j <= n; j++) { dp[j] = Math.min(dp[j], dp[j - i * i] + 1); } } return dp[n]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int numSquares = new LeetCode279().numSquares(n); System.out.println(numSquares); }}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 3
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论