当前位置：首页 > news >正文

代码学习记录31---动态规划开始

news 来源：原创 2024/5/16 12:13:30

随想录日记part31

$t im e ：$ 2024.03.29

主要内容：今天开始要学习动态规划的相关知识了，今天的内容主要涉及四个方面：
理论基础 ; 斐波那契数 ;爬楼梯 ;使用最小花费爬楼梯。

理论基础
509. 斐波那契数
70. 爬楼梯
746. 使用最小花费爬楼梯

关于动态规划的理论知识，我们可以直接去看理论基础对应的链接就可以了。下面主要还是对于题目的讲解。在这里插入图片描述
总结一下核心思想：

对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！
【1】.确定dp数组以及下标的含义
【2】.确定递推公式
【3】.dp数组如何初始化
【4】.确定遍历顺序
【5】.举例推导dp数组

Topic1斐波那契数

题目：

斐波那契数（通常用 $F (n)$ 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
$F (0) = 0 ， F (1) = 1$
$F (n) = F (n - 1) + F (n - 2)$ ，其中 $n > 1$
给定 $n$ ，请计算 $F (n)$ 。

输入： $n = 4$
输出： $3$
解释： $F (4) = F (3) + F (2) = 2 + 1 = 3$

思路：

按照上面的五个步骤给出下面的代码：
代码如下：

class Solution {public int fib(int n) {// 【1】.确定dp数组以及下标的含义int[] dp = new int[n + 1];// dp[n]就是第i个数的斐波那契数值// 【3】.dp数组如何初始化if (n == 0)return 0;if (n == 1)return 1;dp[0] = 0;dp[1] = 1;// 【2】.确定递推公式【4】.确定遍历顺序【5】.举例推导dp数组for (int i = 2; i < n + 1; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

时间复杂度： $O (n)$
空间复杂度： $O (n)$

Topic2爬楼梯

题目：

假设你正在爬楼梯。需要 $n$ 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

输入： $n = 3$
输出： $3$
解释：
有三种方法可以爬到楼顶。
【1】.1 阶 + 1 阶 + 1 阶
【2】. 1 阶 + 2 阶
【3】. 2 阶 + 1 阶
思路：

按照上面的五个步骤给出下面的代码，在注释中给出具体的思路：
整体代码如下：

class Solution {public int climbStairs(int n) {// 【1】.确定dp数组以及下标的含义,这里的dp[i]表示i阶到达楼顶的方法数int[] dp = new int[n + 1];// 【3】.dp数组如何初始化if (n == 1)return 1;if (n == 2)return 2;dp[1] = 1;dp[2] = 2;// 【2】.确定递推公式dp[i]=dp[i-1]+dp[i-2];【4】.确定遍历顺序【5】.举例推导dp数组for (int i = 3; i < n + 1; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

时间复杂度： $O (n)$
空间复杂度： $O (n)$

Topic3使用最小花费爬楼梯

题目：

给你一个整数数组 $cos t$ ，其中 $cos t [i]$ 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

输入： $cos t = [10, 15, 20]$
输出： $15$
解释： 你将从下标为 1 的台阶开始。支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

思路：

举例推导dp数组
拿示例： $cos t = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]$ ，来模拟一下 $d p$ 数组的状态变化，如下：

整体代码如下：

class Solution {public int minCostClimbingStairs(int[] cost) {// 【1】.确定dp数组以及下标的含义// dp[i]表示到达第i个台阶的最低花费钱数int n = cost.length;int[] dp = new int[cost.length + 1];// 【3】.dp数组如何初始化【4】.确定遍历顺序dp[0] = 0;dp[1] = 0;// 【2】.确定递推公式//【4】.确定遍历顺序//【5】.举例推导dp数组for (int i = 2; i < n + 1; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[n];}
}