Cangjie/Exercises动态规划完全指南：从爬楼梯到仓颉递归与DP的本质区别

Cangjie/Exercises动态规划完全指南从爬楼梯到仓颉递归与DP的本质区别【免费下载链接】Exercises本仓收集仓颉算法题解程序项目地址: https://gitcode.com/Cangjie/Exercises本仓库Cangjie/Exercises收集了用仓颉语言Cangjie编写的算法题解其中 思想-动态规划.cj 和 动态规划.cj 覆盖了爬楼梯、打家劫舍、背包问题、最长递增子序列等经典动态规划DP题。本指南将带你从零理解动态规划思想并搞懂递归与动态规划最本质的区别帮你快速上手仓颉 DP 实战。一、动态规划是什么一句话讲透动态规划 把大问题拆成小问题 记住小问题的答案它有两个灵魂特征 最优子结构大问题的最优解由子问题的最优解组成比如爬到第 n 阶的方案数 爬到第 n-1 阶 爬到第 n-2 阶的方案数。重叠子问题递归会反复算同一批子问题DP 用一张表dp 数组把结果缓存起来只算一次。 记忆口诀定义状态 → 写出状态转移方程 → 确定初始值 → 按顺序填表 → 取答案。算法竞赛入门到进阶——本仓库 【图书】算法竞赛入门到进阶 目录收录了配套的仓颉题解是 DP 进阶的好教材二、从爬楼梯开始你的第一道 DP 题爬楼梯是动态规划入门的Hello World每次爬 1 阶或 2 阶问爬到 n 阶有多少种方法状态定义dp[i]表示爬到第 i 阶的方案数。状态转移dp[i] dp[i-1] dp[i-2]阶数 i12345dp[i]12358规律一眼可见这不就是斐波那契数列吗仓颉实现见 climbStairs 方法作者做了一处漂亮的优化——既然dp[i]只依赖前两项就用两个变量滚动代替整张表把空间复杂度从 O(N) 压到O(1)pre2记录dp[i-2]pre1记录dp[i-1]每轮计算cur pre1 pre2然后整体前移一格这是 DP 空间优化的通用套路后面打家劫舍同样适用 ✅三、递归 vs 动态规划最本质的区别很多人分不清递归和 DP其实一句话就能说清源自源码注释的精髓递归和动态规划都是将原问题拆成多个子问题然后求解他们之间最本质的区别是动态规划保存了子问题的解避免重复计算。用一张表对比 对比维度递归动态规划思路方向自顶向下大问题 → 拆子问题自底向上小问题 → 堆出大问题子问题结果默认每次重算除非手动加记忆化存入 dp 表每个子问题只解一次额外开销函数调用栈n 大时易栈溢出仅数组空间可滚压优化本质天然分治分治 缓存Memoization一个直观例子递归求斐波那契fib(n) fib(n-1) fib(n-2)算fib(5)时fib(3)会被重复计算好多次而 DP 填表时dp[3]只算一次后续直接查表。 换句话说递归是过程动态规划是带缓存的结果。带记忆化的递归和自底向上的 DP 殊途同归但 DP 填表写法没有调用栈深度限制更适合刷题。四、DP 题型家族一个方程走遍 LeetCode本仓库 ThinkDynamicPlan 类 用统一思路解了 20 道经典题按状态转移方程可以分成几大题型家族4.1 线性 DP打家劫舍不能偷相邻房屋转移方程dp[i] max(dp[i-2] nums[i], dp[i-1)——偷这家与跳过这家二选一。环形版本 rob2 则拆成两段线性问题取最大值。4.2 二维 DP矩阵路径类最小路径和dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]不同路径数dp[i][j] dp[i-1][j] dp[i][j-1]二维表可以沿边缘滚压成一维minPathSum 就演示了这种写法。4.3 背包 DP0-1 背包经典中的经典dp[i][j] max(dp[i-1][j], dp[i-1][j-w] v)含义是第 i 件物品不放 or 放。仓库里同时给出了二维版与一维滚压版 knapsack / knapsack2一维版从右往左遍历是新手最容易踩的坑 ⚠️4.4 子序列 DP最长递增子序列LISdp[i] max(dp[j] 1)j 为满足nums[j] nums[i]的所有前置位置最长公共子序列LCS字符相同则dp[i][j] dp[i-1][j-1] 1否则取上方与左方的较大值见 longestCommonSubsequence4.5 剑指 Offer 系列swordoffer/动态规划.cj 收录了斐波那契、矩形覆盖、青蛙跳台阶含变态跳台阶进阶版、连续子数组最大和等面试题全部用滚压变量实现代码风格与 LeetCode 篇完全一致适合作为第二遍练习。五、如何在仓颉中高效写 DP结合仓库实现仓颉写 DP 有几个值得注意的点数组初始化的惯用法ArrayInt(n 1, repeat: 0)一行建好 dp 表二维表用构造闭包ArrayArrayInt(rows) { _ ArrayInt(columns, repeat: 0) }见 minPathSum2。闭包嵌套复用环形打家劫舍里内部闭包rob(first, last)复用了同一段线性 DP 逻辑避免代码重复。纯函数 类封装每道题都是一个func按题型分组到ThinkDynamicPlan类中结构清晰、便于测试入口在 main.cj。注释即文档每个函数头部都保留了原题描述// MARK:行标注了状态转移方程读代码就是读题解。项目整体结构说明见 算法思想解题合集/README.md。六、快速开始把仓库拉到本地如果你也想边读源码边运行只需 clone 仓库本仓库为只读题解直接跑即可git clone https://gitcode.com/Cangjie/Exercises.git然后安装仓颉语言工具链进入 算法思想解题合集 目录用仓颉包管理器cjpm管理依赖并运行 main.cj 即可看到各题解的执行过程。七、学习路线建议给新手的一条 DP 进阶路线 第 1 周吃透爬楼梯、斐波那契、矩形覆盖一维线性 DP 滚压优化第 2 周打家劫舍系列、最小路径和、不同路径数二维 DP 与边界初始化第 3 周最长递增子序列、最长公共子序列子序列 DP第 4 周0-1 背包、分割整数、解码方法带选择的 DP配套资源仓库 【图书】算法竞赛入门经典 与 【图书】算法竞赛入门到进阶 目录均收录了对应例题的仓颉实现可作为 DP 之外的算法体系补充。总结动态规划不是玄学而是拆问题 存答案的机械流程。记住递归与 DP 的本质区别——缓存子问题的解——再沿着状态定义 → 转移方程 → 填表取答案四步走配合本仓库的仓颉题解反复对照练习你就能从爬楼梯一路走到背包与子序列的进阶题目。【免费下载链接】Exercises本仓收集仓颉算法题解程序项目地址: https://gitcode.com/Cangjie/Exercises创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考