动态规划（DP）核心原理+解题模板+经典例题详解

动态规划（Dynamic Programming，简称DP）是算法中解决最优子结构问题的核心方法，专门解决暴力递归重复计算、效率极低的痛点问题。

一、动态规划到底是什么？

核心思想：把复杂问题拆分为若干个子问题，缓存/存储子问题的解，避免重复计算，最终推导出原问题的最优解。
本质：空间换时间，通过数组/哈希表存储子问题结果，消除递归中的重复计算。

二、DP适用的三大必要条件（判断标准）

一道题目能使用动态规划，必须同时满足以下3个条件：

重叠子问题
子问题会被多次重复计算（例：递归求斐波那契数，F(5)依赖F(4)、F(3)，F(4)又依赖F(3)，F(3)被重复计算）。
最优子结构
原问题的最优解，可以由子问题的最优解推导得出。
无后效性
子问题的解一旦确定，后续决策不会改变该结果；仅关注子问题的结果，无需关心其求解过程。

三、DP标准解题五步法（万能模板）

这是所有DP题目的固定解题流程，按步骤执行即可理清思路，以斐波那契数列为例讲解：

步骤1：确定状态

定义dp[i]/dp[i][j]的含义（最关键步骤）
例：dp[i] 表示第i个斐波那契数的值

步骤2：确定状态转移方程（递推公式）

写出dp[i]与前置子问题的关系（DP核心公式）
例：dp[i] = dp[i-1] + dp[i-2]

步骤3：确定初始条件（dp数组初始化）

定义最小子问题的解（基础边界值）
例：dp[0] = 0，dp[1] = 1

步骤4：确定计算顺序

两种主流方式：

自底向上：从前往后填表（循环遍历，最常用）
自顶向下：记忆化递归
例：从前到后使用for循环遍历

步骤5：提取最终答案

明确结果对应的dp数组下标
例：return dp[n]

四、经典DP问题实战

4.1 斐波那契数列

题目描述

斐波那契数（F(n)）形成的序列称为斐波那契数列，由0和1开始，后续每一项等于前两项之和：

F(0) = 0，F(1) = 1
F(n) = F(n-1) + F(n-2)（n>1）
给定n，计算F(n)

示例

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

解题代码

class Solution {
    public int fib(int n) {
        // 初始化dp数组，存储子问题的解
        int[] dp = new int[n + 2];
        // 初始条件：最小子问题的解
        dp[0] = 0;
        dp[1] = 1;
        // 自底向上遍历计算
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        // 返回最终结果
        return dp[n];
    }
}

4.2 01背包问题（最经典DP问题）

题目描述

有N件物品和一个容量为V的背包，每件物品只能使用一次；
第i件物品的体积是vi，价值是wi；
求解将哪些物品装入背包，可使总体积不超过背包容量，且总价值最大，输出最大价值。

数据范围

0 < N,V ≤ 1000
0 < vi,wi ≤ 1000

输入样例

输出样例

解题代码

public class Bag01 {
    public static void main(String[] args) {
        // 物品数量
        int n = 4;
        // 背包容量
        int V = 5;
        // 物品体积数组
        int[] weight = {1, 2, 3, 4};
        // 物品价值数组
        int[] value = {2, 4, 4, 5};

        // dp二维数组定义：dp[i][j] = 前i个物品，背包容量为j时的最大价值
        int[][] dp = new int[n + 1][V + 1];

        // 遍历每个物品
        for(int i = 1; i <= n; i++){
            // 遍历所有背包容量
            for(int j = 1; j <= V; j++){
                // 当前背包容量装不下第i个物品 → 不选该物品
                if(j < weight[i-1]){ 
                    dp[i][j] = dp[i-1][j];
                }else{
                    // 装得下 → 选/不选 取最大值
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weight[i-1]] + value[i-1]);
                }
            }
        }
        // 输出最终最大价值
        System.out.println(dp[n][V]); 
    }
}