数据结构与算法刷题之【动态规划】篇
<p>汇总动态规划相关的数据结构与算法刷题笔记，讲解递归、状态定义与转移方程等核心思想，涵盖背包、路径、子序列等经典题型并给出Java实现与优化思路。</p>
标签：动态规划
LeetCode 1137. 第 N 个泰波那契数（动态规划）
<p>本文讲解 LeetCode 第 1137 题「第 N 个泰波那契数」，递推公式为 dp(i)=dp(i-1)+dp(i-2)+dp(i-3)。使用一维数组保存前三项结果进行动态规划求解，时间复杂度 O(n)、空间复杂度 O(n)，并附完整 Java 代码。</p>
LeetCode 198. 打家劫舍（一维线性DP）
<p>本文讲解 LeetCode 第 198 题「打家劫舍」，在不能偷相邻两间房的约束下求最高金额。定义 dp(i) 表示前 i 间房可偷的最高金额，递推式 dp(i)=max(dp(i-1), dp(i-2)+nums[i])，时间复杂度 O(n)，并附 Java 实现。</p>
LeetCode 62. 不同路径（动态规划/递归）
<p>本文讲解 LeetCode 第 62 题「不同路径」，计算机器人从左上角到右下角只能向右或向下走的路径数。给出二维动态规划、朴素递归与记忆化递归三种实现，递推式 dp[i][j]=dp[i-1][j]+dp[i][j-1]，附 Java 代码。</p>
LeetCode 746. 使用最小花费爬楼梯（线性DP）
<p>本文讲解 LeetCode 第 746 题「使用最小花费爬楼梯」，每次可爬一或两阶并支付对应费用，求到达顶部的最小花费。定义 dp(i) 表示到达第 i 阶的最小费用，递推式 dp(i)=min(dp(i-1),dp(i-2))+cost[i]，时间复杂度 O(n)。</p>
LeetCode 790. 多米诺和托米诺平铺（二维DP转一维）
<p>本文讲解 LeetCode 第 790 题「多米诺和托米诺平铺」，用两种骨牌铺满 2×n 面板求方案数。以每列的四种状态建立递推方程，并进一步把二维 DP 优化为一维滚动变量，时间复杂度 O(n)、空间复杂度 O(1)，附 Java 代码。</p>
AcWing 蓝桥杯AB组辅导课 03、数学与简单DP
<p>本文是 AcWing 蓝桥杯 AB 组辅导课第三讲「数学与简单 DP」的学习笔记，数学部分讲解买不到的数目、蚂蚁感冒、饮料换购，DP 部分涵盖 01 背包、摘花生、最长上升子序列、地宫取宝与波动数列等题，均附 Java 题解与推导。</p>
AcWing 蓝桥杯AB组辅导课 09、复杂DP
<p>本文是 AcWing 蓝桥杯 AB 组辅导课第九讲「复杂 DP」的学习笔记，讲解鸣人的影分身线性 DP、糖果背包变形、密码脱落区间 DP、生命之树树形 DP、斐波那契前 n 项和矩阵快速幂，以及包子凑数、括号配对、旅游规划等题解。</p>
动态规划之线性DP
<p>讲解线性动态规划的定义与解题思路，以AcWing数字三角形等模板题为例分析状态定义、初始化与转移方程，总结从上至下和从下至上两种递推方式及滚动数组优化技巧。</p>
动态规划之背包问题
<p>系统讲解背包类动态规划问题，涵盖01背包、完全背包、多重背包与分组背包的分类与区别，结合AcWing模板题给出二维数组与一维滚动数组的Java实现及优化过程。</p>
LeetCode 53. 最大子序和
<p>本文讲解 LeetCode 第 53 题「最大子序和」，分别给出贪心与动态规划两种解法。贪心通过判断当前和是否为正决定是否累加，动规则利用 f(i)=max(f(i-1)+nums[i], nums[i]) 递推，均达到 O(n) 时间复杂度与 O(1) 空间复杂度。</p>
LeetCode 70. 爬楼梯
<p>本文讲解 LeetCode 第 70 题「爬楼梯」，每次可爬 1 或 2 阶，求到达楼顶的方案数。分析得出其规律符合斐波那契数列，使用两个变量滚动保存 f(x-1) 与 f(x-2)，将空间复杂度优化到 O(1)，并附 Java 实现。</p>
LeetCode 338. 比特位计数
<p>本文讲解 LeetCode 第 338 题「比特位计数」，计算 0 到 n 每个数二进制中 1 的个数。介绍 Brian Kernighan 算法及其递推优化、奇偶数判别与字符串替换等方法，可将时间复杂度优化到 O(n)，并附完整 Java 代码。</p>