动态规划

更新2/16/2026

字数0

时长0 分钟

动态规划（dynamic programming）是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。

一、记忆化搜索

1. 题目背景：

leetCode：一个机器人从 m x n 网格的左上角 (1,1) 走到右下角 (m,n)，每次只能向下或向右走，求有多少条不同的路径。

2. 算法拆解

（1）基础思路：深度优先搜索（DFS）

• 递归逻辑：机器人在位置 (m1, n1) 时，只有两种选择：向下走 (m1+1, n1) 或向右走 (m1, n1+1)。

• 终止条件：

  • 若走出网格（m1>m 或 n1>n），路径无效，返回 0；
  • 若到达终点 (m,n)，找到一条有效路径，返回 1。

• 核心公式：当前位置路径数 = 向下走的路径数 + 向右走的路径数。

（2）优化：记忆化搜索（Memoization）

单纯的 DFS 会存在大量重复计算（比如不同路径会走到同一个位置 (m1, n1)，重复递归计算该位置的路径数），因此代码中加入了 memor 数组：

• memor[m1][n1] 存储位置 (m1, n1) 到终点的路径数；
• 每次递归前先检查 memor[m1][n1]，若不为 0（已计算过），直接返回缓存值，避免重复递归；
• 计算完当前位置的路径数后，存入 memor 数组，供后续复用。

3. 代码实现

class Solution {
    public int uniquePaths(int m, int n) {
        // 初始化记忆化数组，大小 (m+1)x(n+1)（因为坐标从1开始）
        int[][] memor = new int[m+1][n+1];
        // 从起点(1,1)开始递归
        return dfs(m, n, 1, 1, memor);
    }

    public int dfs(int m, int n, int m1, int n1, int[][] memor) {
        // 终止条件1：走出网格，路径无效
        if (m1 > m || n1 > n) {
            return 0;
        }

        // 终止条件2：到达终点，找到1条有效路径
        if (m1 == m && n1 == n) {
            return 1;
        }

        // 记忆化核心：如果当前位置已计算过，直接返回缓存值
        if (memor[m1][n1] != 0) {
            return memor[m1][n1];
        }

        // 递归计算向下走的路径数
        int f1 = dfs(m, n, m1 + 1, n1, memor);
        // 递归计算向右走的路径数
        int f2 = dfs(m, n, m1, n1 + 1, memor);
        // 缓存当前位置的路径数（向下+向右）
        memor[m1][n1] = f1 + f2;
        // 返回当前位置的总路径数
        return f1 + f2;
    }
}

例题

1. 爬楼梯

题目介绍：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 ：

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

代码实现

方法一：记忆化搜索（暴力递归+备忘录记录）

时间复杂度：o(n)，空间复杂度：o(n)

1. 当首次计算 时，我们将其记录至 memo[n] ，以便之后使用。
2. 当再次需要计算 时，我们便可直接从 memo[n] 中获取结果，从而避免重复计算该子问题。

class Solution {
    public int climbStairs(int n) {
        // 备忘录
        int[] memo = new int[n + 1];
        return dfs(memo, n);
    }


    // 置顶向下递归，通过备忘录将时间复杂度从指数级别降低至o(n);
    public int dfs(int[] memo, int n) {
        if (n <= 0) {
            return 0;
        }

        // 备忘录查询
        if (memo[n] != 0) {
            return memo[n];
        }

        // 出口
        if (n == 1 || n == 2) {
            return n;
        }

        // 记录备忘录
        return memo[n] = dfs(memo, n - 1) + dfs(memo, n - 2);
    }
}

方法二：动态规划

时间复杂度：o(n)，空间复杂度：o(n)

记忆化搜索的 “迭代版”—— 把递归的子问题顺序反过来，从最小的子问题开始迭代计算，核心是无重复地递推所有子问题

由于动态规划不包含回溯过程，因此只需使用循环迭代实现，无须使用递归。在以下代码中，我们初始化一个数组 dp 来存储子问题的解，它起到了与记忆化搜索中数组 memo 相同的记录作用：

class Solution {
    public int climbStairs(int n) {
        // 特殊情况处理
        if(n==1 || n==2){
            return n;
        }
        //初始化dp数组，设置最小问题解。
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        // 状态转移：大问题依赖于小问题的解集
        for(int i=3;i<=n;i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

}

方法三：动态规划（优化空间）

时间复杂度：o(n)，空间复杂度：o(1)

由于 只与 和 有关，因此我们无须使用一个数组 dp 来存储所有子问题的解，而只需两个变量滚动前进即可。代码如下所示：

class Solution {
    public int climbStairs(int n) {
        // 特殊情况处理
        if (n == 1 || n == 2) {
            return n;
        }

        int d = 1, p = 2;

        // 状态转移：大问题依赖于小问题的解集
        for (int i = 3; i <= n; i++) {
            // 两个变量滚动记录
            int q = d + p;
            d = p;
            p = q;
        }
        return p;
    }

}

2. 最长回文子串

题目介绍：

给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 ：

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"

算法实现

方法一：中心扩展法(推荐)

时间复杂度：O(n²)，空间复杂度： O(1)

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        
        int start = 0;
        int end = 0;
        
        for (int i = 0; i < s.length(); i++) {
            // 以单个字符为中心扩展(处理奇数长度回文)
            int len1 = expandAroundCenter(s, i, i);
            // 以两个字符之间为中心扩展(处理偶数长度回文)
            int len2 = expandAroundCenter(s, i, i + 1);
            
            int len = Math.max(len1, len2);
            
            // 更新最长回文子串的起始和结束位置
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        
        return s.substring(start, end + 1);
    }
    
    // 从中心向两边扩展,返回回文长度
    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // 返回回文长度
        return right - left - 1;
    }
}

3. 编辑距离

题目介绍：

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符

• 删除一个字符

• 替换一个字符

示例 ：

示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

代码实现

方法一：记忆化搜索

时间复杂度：O(nm)，空间复杂度： O(nm)

题目的三种操作可以抽线为以下操作

• dfs(n - 1, m) = 删除一个元素
• dfs(n, m - 1) = 添加一个元素
• dfs(n - 1, m - 1) = 修改一个元素

class Solution {
    private char[] w1, w2;
    private int[][] memo;

    public int minDistance(String word1, String word2) {
        w1 = word1.toCharArray();
        w2 = word2.toCharArray();
        int n = w1.length;
        int m = w2.length;
        memo = new int[n][m];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(n - 1, m - 1);
    }

    public int dfs(int n, int m) {

        if (m < 0) {
            return n + 1;
        }

        if (n < 0) {
            return m + 1;
        }

        if (memo[n][m] != -1) {
            return memo[n][m];
        }

        if (w1[n] == w2[m]) {
            // 这里相当符合条件，不需要调整。
            return memo[n][m] = dfs(n - 1, m - 1);
        }

        // 关键！！！
        // dfs(n - 1, m) = 删除一个元素
        // dfs(n, m - 1) = 添加一个元素
        // dfs(n - 1, m - 1) = 修改一个元素
        return memo[n][m] = Math.min(Math.min(dfs(n - 1, m), dfs(n, m - 1)), dfs(n - 1, m - 1)) + 1;
    }
}