动态规划lc

embedded/2024/12/22 21:46:24/

先找到规律,然后找边界情况;部分特殊情况分类讨论  *递归

70.爬楼梯

简单

提示

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

示例 1:

输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2:

输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示:

  • 1 <= n <= 45

方法一:动态规划
思路和算法

我们用 f(x) 表示爬到第 x 级台阶的方案数,考虑最后一步可能跨了一级台阶,也可能跨了两级台阶,所以我们可以列出如下式子:

f(x)=f(x−1)+f(x−2)

它意味着爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。很好理解,因为每次只能爬 1 级或 2 级,所以 f(x) 只能从 f(x−1) 和 f(x−2) 转移过来,而这里要统计方案总数,我们就需要对这两项的贡献求和。

以上是动态规划的转移方程,下面我们来讨论边界条件。我们是从第 0 级开始爬的,所以从第 0 级爬到第 0 级我们可以看作只有一种方案,即 f(0)=1;从第 0 级到第 1 级也只有一种方案,即爬一级,f(1)=1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。我们不妨写几项来验证一下,根据转移方程得到 f(2)=2,f(3)=3,f(4)=5,……,我们把这些情况都枚举出来,发现计算的结果是正确的。

我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n) 的实现,但是由于这里的 f(x) 只和 f(x−1) 与 f(x−2) 有关,所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)。下面的代码中给出的就是这种实现。

509. 斐波那契数

尝试过

简单

相关标签

相关企业

斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1

给定 n ,请计算 F(n) 。

这个就是只有第三个才开始变成斐波那契,所以应该分类讨论

class Solution {public int fib(int n) {if(n<2){return n;}int p=0;int q=0;int r=1;for (int i=2;i<=n;i++){p=q;q=r;r=p+q;}return r;}
}

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下: 

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n,请返回第 n 个泰波那契数 Tn 的值。

示例 1:

输入:n = 4
输出:4
解释:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
class Solution {public int tribonacci(int n) {if (n==0){return 0;}if (n<=2){return 1;}int i=0,j=0,k=1,r=1;//每次设定的时候,保留一次for循环里的滚动一次,即多一位0(其实i是任意数字都没关系)for (int m=3;m<=n;m++){//记得从第几个tri开始i=j;j=k;k=r;r=i+j+k;}return r;}
}


http://www.ppmy.cn/embedded/126549.html

相关文章

YOLOv8 基于NCNN的安卓部署

YOLOv8 NCNN安卓部署 前两节我们依次介绍了基于YOLOv8的剪枝和蒸馏 剪枝&#xff1a;https://blog.csdn.net/qq_41335232/article/details/140823592 蒸馏&#xff1a;https://blog.csdn.net/qq_41335232/article/details/142717122 开源代码&#xff1a;li554/yolov8_depl…

Java面向对象编程--高级

目录 一、static关键字 1.1 静态变量 1.2 静态内存解析 1.3 static的应用与练习 二、单例设计模式 2.1 单例模式 2.2 如何实现单例模式 三、代码块 3.1 详解 3.2 练习&#xff0c;测试 四、final关键字 五、抽象类与抽象方法 5.1 abstract 5.2 练习 六、接口 6.…

蓝牙定位的MATLAB仿真程序(基于信号强度,平面内的定位,四个蓝牙基站)

这段代码通过RSSI信号强度实现了蓝牙定位,展示了如何使用锚点位置和测量的信号强度来估计未知点的位置。它涵盖了信号衰减模型、距离计算和最小二乘法估计等基本概念。通过图形化输出,用户可以直观地看到真实位置与估计位置的关系。 文章目录 蓝牙定位原理蓝牙定位的原理优缺…

2.1 HTML5 - Canvas标签

文章目录 引言Canvas标签概述定义实例&#xff1a;创建画布 理解Canvas坐标系概述实例&#xff1a;获取Canvas坐标 获取Canvas环境上下文概述实例&#xff1a;获取Canvas环境上下文设置渐变色效果 结语 引言 大家好&#xff0c;今天我们要一起探索HTML5中一个非常有趣且强大的…

【TouchSocket 和 client.GetStream 区别】

TouchSocket 和 client.GetStream() 是用于网络通信的不同工具和方法&#xff0c;但它们的功能层面和适用范围也有明显区别。下面我来详细解释 TouchSocket 和 client.GetStream() 的差异。 1. TouchSocket TouchSocket 是一个完整的 网络通信框架&#xff0c;专注于为开发者…

构建流媒体管道:利用 Docker 部署 Nginx-RTMP 从 FFmpeg RTMP 推流到 HLS 播放的完整流程

最近要实现一个类似导播台的功能&#xff0c;于是我先用 FFmpeg 实现一个参考对照的 Demo&#xff0c;我将其整理为一篇文章&#xff0c;方便后续大家或者和自己参考&#xff01; 1、软件工具介绍 本次部署相关软件 / 工具如下&#xff1a; FFmpeg&#xff1a;全称是 Fast Fo…

Unity修改鼠标图片【超简单】

1.向Unity导入需要修改的鼠标图片&#xff0c;在Unity内设置图片的Texture Type为Cursor。 2.编写代码 [SerializeField] Texture2D mouseTex;//放图片 void Start() {Cursor.SetCursor(mouseTex, Vector2.zero, CursorMode.Auto); }3.代码挂载在某物体&#xff08;或者随便哪…