代码随想录 Day38 - 动态规划（一）

作者：jjn0703

2023-08-06
江苏
本文字数：1337 字
阅读完需：约 4 分钟

理论基础

概念

动态规划，英文：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);        }    }}

复制代码

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/d6df780d55f5879d1157564ff】。

jjn0703

关注

Java工程师/终身学习者 2018-03-26 加入

USTC硕士/健身健美爱好者/Java工程师.

发布

暂无评论

创作场景

代码随想录 Day38 - 动态规划（一）

理论基础

概念

解题步骤

作业题

509. 斐波那契数

70. 爬楼梯

746. 使用最小花费爬楼梯

jjn0703

评论