理论基础
概念
动态规划，英文：Dynamic Programming，简称 DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
解题步骤
- 确定 dp 数组（dp table）以及下标的含义
- 确定递推公式
- dp 数组如何初始化
- 确定遍历顺序
- 举例推导 dp 数组
作业题
509. 斐波那契数
package jjn.carl.dp; import java.util.Scanner; /** * @author Jjn * @since 2023/8/4 23:44 */ public class LeetCode509 { public int fib(int n) { if (n <= 1) { return n; } int[] dp = new int[2]; dp[1] = 1; int sum = 0; for (int i = 2; i <= n; i++) { sum = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = sum; } return sum; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); int fib = new LeetCode509().fib(n); System.out.println(fib); } } }
70. 爬楼梯
package jjn.carl.dp; import java.util.Scanner; /** * @author Jjn * @since 2023/8/4 23:52 */ public class LeetCode70 { public int climbStairs(int n) { if (n <= 1) { return n; } int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); System.out.println(new LeetCode70().climbStairs(n)); } } }
746. 使用最小花费爬楼梯
package jjn.carl.dp; import java.util.Scanner; /** * @author Jjn * @since 2023/8/4 23:56 */ public class LeetCode746 { public int minCostClimbingStairs(int[] cost) { int[] dp = new int[cost.length + 1]; dp[0] = 0; dp[1] = 0; for (int i = 2; i <= cost.length; i++) { dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); } return dp[cost.length]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int total = scanner.nextInt(); int[] cost = new int[total]; for (int i = 0; i < total; i++) { cost[i] = scanner.nextInt(); } int minCostClimbingStairs = new LeetCode746().minCostClimbingStairs(cost); System.out.println(minCostClimbingStairs); } } }
