一维DP深度解析

动态规划（Dynamic Programming，DP）是算法设计中的重要思想，通过将复杂问题分解为重叠子问题，并利用子问题的解高效推导原问题答案。其中一维动态规划是最基础也最常用的形式——仅需一个一维数组存储子问题的解，就能“以空间换时间”解决一系列经典问题。

一、一维动态规划基础知识

1.1 核心思想

一维动态规划的核心是**“用已知子问题的解推导当前问题的解”**，具体表现为：

• 分解问题：将原问题（规模为n）分解为规模更小的子问题（如规模n-1、n-2）。
• 定义状态：用dp[i]表示“规模为i的子问题的解”（一维数组存储）。
• 递推关系：找到dp[i]与dp[i-1]、dp[i-2]等前驱状态的关系（核心难点）。
• 边界条件：确定最小规模子问题的解（如dp[0]、dp[1]），作为递推的起点。

相比递归（可能重复计算子问题），一维DP通过存储子问题的解，将时间复杂度从指数级降至线性或线性对数级。

1.2 适用场景

一维DP适用于以下特征的问题：

1. 问题与规模相关：解依赖于更小规模的同类问题（如“前i个元素的最优解”）。
2. 子问题重叠：不同规模的问题会共享相同的子问题（如斐波那契数列中f(5)和f(6)都依赖f(4)）。
3. 无后效性：子问题的解一旦确定，就不会受后续计算影响（如dp[i]确定后，不依赖dp[i+1]）。

典型场景：斐波那契数列、爬楼梯、最长递增子序列、打家劫舍等。

二、经典案例详解

2.1 案例1：斐波那契数列（入门级）

问题描述

求斐波那契数列的第n项，定义为：

• f(0) = 0，f(1) = 1
• f(n) = f(n-1) + f(n-2)（n ≥ 2）

动态规划设计

1. 定义状态：dp[i]表示第i项斐波那契数。
2. 递推关系：dp[i] = dp[i-1] + dp[i-2]（直接由定义得到）。
3. 边界条件：dp[0] = 0，dp[1] = 1。

代码实现

public class Fibonacci {
    public int fib(int n) {
        if (n <= 1) {
            return n;  // 边界条件直接返回
        }
        // 定义dp数组存储子问题的解
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        // 从2开始递推
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Fibonacci solution = new Fibonacci();
        System.out.println(solution.fib(5));  // 输出5（0,1,1,2,3,5）
    }
}

优化：空间压缩

由于dp[i]仅依赖dp[i-1]和dp[i-2]，无需存储整个数组，用两个变量即可：

public int fibOptimized(int n) {
    if (n <= 1) {
        return n;
    }
    int prevPrev = 0;  // dp[i-2]
    int prev = 1;      // dp[i-1]
    for (int i = 2; i <= n; i++) {
        int current = prev + prevPrev;
        prevPrev = prev;
        prev = current;
    }
    return prev;
}

• 时间复杂度：$O(n)$（遍历一次）。
• 空间复杂度：优化后从$O(n)$降至$O(1)$。

2.2 案例2：爬楼梯（基础应用）

问题描述

每次可以爬1或2个台阶，求爬到第n级台阶的不同方法数。

动态规划设计

1. 定义状态：dp[i]表示爬到第i级台阶的方法数。
2. 递推关系：
   最后一步要么从i-1级爬1级，要么从i-2级爬2级，因此：
   dp[i] = dp[i-1] + dp[i-2]
3. 边界条件：
   • dp[1] = 1（仅1种方法：爬1级）
   • dp[2] = 2（两种方法：1+1或2）

代码实现

public class ClimbStairs {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        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];
    }

    public static void main(String[] args) {
        ClimbStairs solution = new ClimbStairs();
        System.out.println(solution.climbStairs(4));  // 输出5（1+1+1+1等5种）
    }
}

思路拓展

若每次可爬1、2、3个台阶，递推关系变为：
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]（需相应调整边界条件）。

2.3 案例3：打家劫舍（中等难度）

问题描述

沿街有一排房屋，不能抢劫相邻的房屋，求能抢劫到的最大金额。

动态规划设计

1. 定义状态：dp[i]表示抢劫前i间房屋的最大金额。
2. 递推关系：
   • 若抢劫第i间房屋，则不能抢劫第i-1间，金额为dp[i-2] + nums[i-1]（nums下标从0开始）。
   • 若不抢劫第i间房屋，则金额为dp[i-1]。
     因此：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
3. 边界条件：
   • dp[0] = 0（0间房屋，金额0）
   • dp[1] = nums[0]（仅1间房屋，抢它）

代码实现

public class RobHouse {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            // 选择：抢第i间（i-1下标）或不抢
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[n];
    }

    public static void main(String[] args) {
        RobHouse solution = new RobHouse();
        int[] nums = {2, 7, 9, 3, 1};
        System.out.println(solution.rob(nums));  // 输出12（抢2+9+1）
    }
}

空间优化

dp[i]仅依赖dp[i-1]和dp[i-2]，用两个变量压缩空间：

public int robOptimized(int[] nums) {
    if (nums.length == 0) return 0;
    int prevPrev = 0;  // dp[i-2]
    int prev = nums[0]; // dp[i-1]
    for (int i = 2; i <= nums.length; i++) {
        int current = Math.max(prev, prevPrev + nums[i - 1]);
        prevPrev = prev;
        prev = current;
    }
    return prev;
}

2.4 案例4：最长递增子序列（LIS，进阶应用）

问题描述

求数组中最长的严格递增子序列的长度（子序列可不连续）。

动态规划设计

1. 定义状态：dp[i]表示以nums[i]为结尾的最长递增子序列长度。
2. 递推关系：
   对于所有j < i，若nums[j] < nums[i]，则dp[i]可由dp[j] + 1更新，取最大值：
   dp[i] = max(dp[j] + 1) （j < i 且 nums[j] < nums[i]）
   若没有符合条件的j，则dp[i] = 1（自身为子序列）。
3. 边界条件：所有dp[i]初始化为1（每个元素至少是自身的子序列）。

代码实现

public class LongestIncreasingSubsequence {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        // 初始化：每个元素自身是长度为1的子序列
        Arrays.fill(dp, 1);
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            // 遍历所有前驱元素j
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequence solution = new LongestIncreasingSubsequence();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(solution.lengthOfLIS(nums));  // 输出4（2,3,7,18）
    }
}

复杂度分析

• 时间复杂度：$O(n^2)$（两层循环，i遍历n次，j遍历i次）。
• 空间复杂度：$O(n)$（dp数组存储n个状态）。
  （注：该问题可通过二分查找优化至$O(n\log n)$，但核心仍是一维DP思想。）

三、一维DP的设计步骤与技巧

3.1 通用设计步骤

1. 明确问题目标：确定要求解的“最优值”“方案数”等（如最大和、最长长度）。
2. 定义状态dp[i]：关键是让dp[i]能表示“规模为i的子问题”，通常与“前i个元素”相关。
3. 推导递推关系：
   思考“如何用dp[0..i-1]得到dp[i]”，可从“最后一步操作”入手（如爬楼梯的最后一步是1级还是2级）。
4. 确定边界条件：初始化最小规模子问题的解（如dp[0]、dp[1]）。
5. 计算并优化：先实现基础版本，再通过“滚动变量”压缩空间（若状态仅依赖少数前驱）。

3.2 常见误区与解决

• 状态定义模糊：若递推关系难以推导，可能是dp[i]定义不合理。例如“打家劫舍”中，dp[i]定义为“前i间房屋”而非“第i间房屋”，更易找到递推关系。
• 忽略边界条件：如n=0或n=1的特殊情况，需在代码中单独处理。
• 过度优化：先实现基础版本保证正确性，再考虑空间优化（避免因优化导致逻辑混乱）。

总结
一维DP是理解DP思想的入门钥匙，其核心是通过定义状态和递推关系，将复杂问题拆解为可逐步求解的子问题，始终遵循“分解-定义-递推-优化”的逻辑。

That’s all, thanks for reading~~
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～