22.爬楼梯：动态规划的Hello World-云帆数科

一、问题引入爬楼梯是动态规划的经典入门问题题目描述如下有10级台阶一次只能走1步或2步请问一共有多少种走法二、动态规划思路解析动态规划的核心是记录子问题答案避免重复计算我们可以通过递推的方式逐步求解初始状态第1级台阶只有1种走法直接走1步即dp[1] 1第2级台阶有2种走法走两次1步或直接走2步即dp[2] 2递推公式走到第n级台阶的走法等于走到第n-1级的走法再走1步加上走到第n-2级的走法再走2步即dp[n] dp[n-1] dp[n-2]计算过程按照递推公式逐步计算dp[3] dp[2] dp[1] 2 1 3dp[4] dp[3] dp[2] 3 2 5dp[5] dp[4] dp[3] 5 3 8dp[6] dp[5] dp[4] 8 5 13dp[7] dp[6] dp[5] 13 8 21dp[8] dp[7] dp[6] 21 13 34dp[9] dp[8] dp[7] 34 21 55dp[10] dp[9] dp[8] 55 34 89三、代码实现1. C语言实现#include stdio.h int main() { int dp[11]; dp[0] 1; // 边界条件第0级台阶有1种走法不走 dp[1] 1; for (int i 2; i 10; i) { dp[i] dp[i-1] dp[i-2]; } printf(10级台阶的走法总数%d\n, dp[10]); return 0; }2. Python实现def climb_stairs(n): if n 1: return 1 dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n 1): dp[i] dp[i-1] dp[i-2] return dp[n] print(10级台阶的走法总数, climb_stairs(10))3. 空间优化版C语言#include stdio.h int main() { int a 1, b 2; if (10 1) { printf(10级台阶的走法总数1\n); return 0; } for (int i 3; i 10; i) { int c a b; a b; b c; } printf(10级台阶的走法总数%d\n, b); return 0; }四、总结动态规划的核心是拆分问题记录子问题结果避免重复计算。爬楼梯问题的递推公式为dp[n] dp[n-1] dp[n-2]本质是斐波那契数列的应用。可以通过空间优化将空间复杂度从O(n)降低到O(1)。点赞收藏关注获取更多算法入门内容

企业数字化 ERP 产品动态

相关推荐

MES/WMS集成投标书：基于InfluxDB与Node.js的实时数据中枢设计

简介：本资源为上海明匠智能系统有限公司编制的《MES和WMS系统项目技术投标书》，面向制造业数字化转型从业者、智能制造系统集成工程师、企业IT规划人员及投标方案撰写人员，聚焦解决彩电等离散制造行业在工业4.0背景下面临的产线协同弱、仓储响… · 2026/9/26 8:52:58

告别DeepSeek服务器繁忙：从API接入到本地部署的完整指南

最近DeepSeek是真的火，火到什么程度呢？白天打开网页版，十个里有八个时间在转圈，然后弹出一句熟悉的“服务器繁忙，请稍后再试。”你说它没服务吧，凌晨两三点又能秒回；你说它服务好吧，… · 2026/9/26 8:52:58

Forcecon-FCVP数字孪生工厂实战：以虚控实的工业级落地指南

简介：本资源是一份面向智能制造领域工程师与数字化转型从业者的「数字孪生工厂解决方案」技术文档，聚焦解决现代化工厂因系统分散、信息不透明导致的管理低效问题。文档系统阐述了基于力控工业采集网关、ForceControl/pSpace平台及Forcecon-FCVP三维可视… · 2026/9/26 8:52:58

MMU、IOMMU、SMMU区别与联系：从地址翻译到设备隔离

这三个缩写放在一起，很容易让人以为只是同一个东西在不同公司的花名。但实际上 MMU、IOMMU、SMMU 虽然干的都是“地址翻译”这件事，服务的对象和解决问题的层次完全不同。尤其很多人在 JZ2440 这类 ARM9 板子上第一次接触 MMU，紧接着又听别人… · 2026/9/26 9:36:13

AnyTXT本地全文检索工具深度解析：Rust+SQLite架构与中文优化实践

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 9:36:13

video-use：视频工程化实践方法论与四大支柱工具协同

1. “video-use”不是功能模块，而是一套视频工程实践方法论你搜“video-use”，页面上跳出来的全是 ffmpeg、yt-dlp、EDL、ElevenLabs 这些词——没有文档、没有 GitHub 仓库、没有 npm 包，甚至连一个像样的 README 都找不到。我第一次看到这个… · 2026/9/26 9:36:13