代码随想录刷题|动态规划理论基础 LeetCode 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯(下)

简介: 代码随想录刷题|动态规划理论基础 LeetCode 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯

70. 爬楼梯

题目链接:力扣

思路


本题也是动态规划的简单题,但是从这一道题目就可以发现动态规划的难点就在于去发现递推公司,这道题目本质上是一道斐波那契数列,但是发现并不容易,推导起来也不是很好想


       题目中要求的每次可以爬1或者2个台阶,也就是说,最终到达n阶台阶有两种方式,一个是爬1阶台阶到达(对应的是从n-1阶台阶开始),那么另一个就是爬2阶台阶到达(对应的是从n-2阶台阶开始爬),而爬n-1阶和n-2阶台阶的方法有dp[n - 1],dp[n - 2]个。所以最终爬n阶台阶的方法种类就是dp[n -1 ]+dp[n -2]。其实也就是从n-1和n-2阶爬上去,探究的是几种走法,而不是几步


       台阶   几种方法

          1          1

          2          2

          3          3

          4          5

          5          8


       从二阶到四阶的那二阶一步和从三阶到四阶的一阶一步本身没有产生新方法,所以是从二阶达到四阶和从三阶达到四阶的两种方式相加


       所以推导的过程是:

               在到达第n层的上一步,我们只有两个选择,走一步,或者走两步。

               如果是走一步,我们需要先通过 f(n-1)种方式到达 n-1 层

               如果是走两步, 我们需要通过 f(n-2)种方式到达第 n - 2 层

               所以综上有 f(n) = f(n-2) + f(n-1)


       至于要如何初始化dp[0] = 1还是dp[1] = 1 .我倒觉得这个不是大问题,只不过是在对代码的意义上的解释不同,dp[1] = 1更能体现出动态思路的意义,dp[0] = 1也没啥问题


爬楼梯

动态规划(优化数组)


class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        // 创建dp数组
        int[] dp = new int[3];
        // 初始化数组
        dp[1] = 1;
        dp[2] = 2;
        // 遍历更新数组
        for (int i = 3; i <= n; i++) {
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
}

动态规划(变量替代数组)

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int dp1 = 1;
        int dp2 = 2;
        for (int i = 3; i <= n; i++) {
            int temp = dp1 + dp2;
            dp1 = dp2;
            dp2 = temp;
        }
        return dp2;
    }
}


746. 使用最小花费爬楼梯

题目链接:力扣

思路

   确定dp数组、确定递推公式、初始化dp真的是不容易呀


1、明确数组


       本体要求的是爬到某一台阶需要的最小花费,随意我们明确dp[]数组为 最小花费数组,其中下标i上的数代表到大第 i 层台阶需要花费的最小费用为 dp[i]


2、递推公式


       数组明确之后,就是考虑怎么获取数组中的值,也就是怎么求取每个台阶的最小花费值。这里dp[i] 是有两种情况的

       第一种情况是从前一个台阶跳上来,那最小花费 = 到达前一个台阶的最小花费 + 前一个台阶对应的费用,也就是 dp[i] = dp[i - 1] + cost[i - 1]

       第二种情况是从前两个台阶跳上来,那最小花费 = 到达前两个台阶的最小花费 + 前两个台阶对应的费用,也就是 dp[i] = dp[i - 2] + cost[i - 2]

       那这两种情况中最小的,就是我们要求的当前台阶对应的最小的费用


3、初始化dp数组


       首先要明确一点就是,当站在下标【0】和下标【1】的时候是不消耗费用的,只有向上跳才会消耗费用,所以这里的初始化是比较重要的,要不然后面的结果也就不同了


01683aaf8a5942d0ad5cf9a1bac03413.png


使用最小花费爬楼梯

动态规划(使用数组)

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // 定义数组
        int[] dp = new int[cost.length + 1];
        // 初始化数组
        dp[0] = 0;
        dp[1] = 0;
        // 遍历填充dp数组
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.min(dp[i-1] + cost[i-1],dp[i -2] + cost[i-2]);
        }
        return dp[cost.length];
    }
}

动态规划(使用变量)

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // 初始化
        int dp0 = 0;
        int dp1 = 0;
        // 遍历更新
        for (int i = 2; i <= cost.length; i++) {
            int dpi = Math.min(dp1 + cost[i-1],dp0 + cost[i-2]);
            dp0 = dp1;
            dp1 = dpi;
        }
        return dp1;
    }
}
相关文章
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
26 1
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
4月前
|
Python
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
28 1
|
4月前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
32 0
【Leetcode刷题Python】73. 矩阵置零
|
4月前
|
Python
【Leetcode刷题Python】1467. 两个盒子中球的颜色数相同的概率
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
44 0
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
58 6
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
52 4
|
4月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
65 7