动态规划DP入门详解（从原理到实战，新手必看）
动态规划入门详解（从原理到实战，新手必看）
动态规划问题（Dynamic Programming，简称DP）应该是很多读者头疼的，但这类问题也是最具技巧性、最有意思的。动态规划作为运筹学的一种最优化方法，在计算机算法中应用广泛，比如最长递增子序列、最小编辑距离等经典问题，都离不开动态规划的思想。
本文将彻底解决三个核心问题，帮你打通动态规划的任督二脉：
- 动态规划到底是什么？
- 解决动态规划问题有什么固定技巧？
- 新手该如何高效学习动态规划？
刷题刷多了就会发现，算法技巧就那几个套路。后续的动态规划系列文章，都会围绕本文的解题框架展开，掌握了这套思路，再难的DP问题也能迎刃而解。所以本文作为DP入门第一章，希望能成为你解决动态规划问题的指导方针，下面直接上干货！
一、动态规划的核心本质
首先明确：动态规划问题的一般形式就是求最值。无论是最长、最小、最多、最少，只要题目要求“最值”，大概率就是动态规划问题。
既然是求最值，核心问题是什么？答案很简单：穷举。因为要找最值，必须先把所有可行的答案穷举出来，再从里面筛选出最值。
看到这里你可能会疑惑：动态规划不就是穷举吗？为什么我遇到的DP问题都那么难？
其实难的不是穷举本身，而是如何“聪明地穷举”——动态规划的穷举，需要满足两个前提，还要掌握一个核心技巧：
- 最优子结构：原问题的最值，可以通过子问题的最值推导得到（子问题之间互相独立，无相互制约）；
- 重叠子问题：暴力穷举会重复计算大量相同子问题，效率极低，需要通过“备忘录”或“DP table”优化；
- 状态转移方程：这是DP的核心，也是最难的一步，它定义了“如何通过子问题推导原问题”，本质就是穷举的规则。
重叠子问题、最优子结构、状态转移方程，就是动态规划的三要素。其中，写出状态转移方程是重中之重。
DP解题思维框架（必背）
为了帮你快速梳理状态转移方程，我总结了一套固定思维框架，按步骤走，就能逐步推出解法：
- 定义dp数组及下标含义；
- 确定递归公式（状态转移）；
- 初始化dp数组；
- 确定遍历顺序；
- 举例推导dp数组；
掌握这个框架后，DP解法的代码就会呈现出固定模板，分为两种形式：
1. 自顶向下递归（带备忘录）
# 自顶向下递归的动态规划defdp(状态1, 状态2,...):for 选择 in 所有可能的选择:# 此时的状态已经因为做了选择而改变 result = 求最值(result, dp(状态1, 状态2,...))return result 2. 自底向上迭代（DP table）
# 自底向上迭代的动态规划# 初始化 base case（最基础、无需推导的子问题） dp[0][0][...]= base case# 进行状态转移（从base case逐步推导到原问题）for 状态1in 状态1的所有取值： for 状态2in 状态2的所有取值： for... dp[状态1][状态2][...]= 求最值(选择1，选择2...)下面通过两个经典案例，详解动态规划的三要素和解题框架——斐波那契数列（理解重叠子问题）、凑零钱问题（掌握状态转移方程）。
二、案例一：斐波那契数列（理解重叠子问题）
力扣第509题「斐波那契数」，是理解重叠子问题的最佳案例。请不要嫌弃它简单，简单案例才能让你集中精力关注算法背后的思想，而非复杂细节。
说明：斐波那契数列严格来说不是动态规划问题（因为没有求最值），但它的递归结构中存在大量重叠子问题，是讲解“优化重叠子问题”的绝佳例子。
1. 暴力递归（低效版）
斐波那契数列的数学递归公式为：f(n) = f(n-1) + f(n-2)，base case为f(0)=0、f(1)=1（力扣题目定义）。
直接翻译成代码如下：
# 计算第n个斐波那契数 intfib(int n){ // base case：最基础的子问题，直接返回结果if(n ==0|| n ==1){ return n;}// 递归推导：原问题 = 子问题1 + 子问题2returnfib(n -1)+fib(n -2);}低效原因：大量重叠子问题
假设n=20，画出递归树就能发现问题：要计算f(20)，需要先算f(19)和f(18)；要算f(19)，需要先算f(18)和f(17)……以此类推。
其中，f(18)被计算了两次，f(17)被计算了三次，且以f(18)为根的递归树体量巨大，重复计算会耗费大量时间。
时间复杂度分析
- 子问题个数：递归树是一棵高度为n的二叉树，节点总数为O(2ⁿ)（指数级别）；
- 单个子问题时间：仅一个加法操作，O(1)；
- 总时间复杂度：O(2ⁿ)，指数爆炸，效率极低。
2. 带备忘录的递归（优化重叠子问题）
既然低效的原因是重复计算，那就用一个「备忘录」，记录已经计算过的子问题答案。每次遇到子问题，先查备忘录，有结果直接用，无结果再计算并存入备忘录。
备忘录可以用一维数组（适合子问题是单个整数的情况）或哈希表实现，这里用一维数组更高效。
#include<vector>usingnamespace std;intfib(int n){ 
