编辑“︁一维动态规划”︁

{{DISPLAYTITLE:一维动态规划}}  
'''一维动态规划'''是[[动态规划]]中最基础的形式之一，通过使用一维数组（或变量）存储子问题的解，避免重复计算，从而高效解决具有[[最优子结构]]和[[重叠子问题]]特性的问题。本章将详细介绍其核心思想、实现方法及典型应用场景。

== 基本概念 ==  
动态规划（Dynamic Programming, DP）通过将复杂问题分解为相互关联的子问题，并存储子问题的解（称为“记忆化”），实现高效求解。'''一维动态规划'''特指状态转移仅依赖前一维状态的DP问题，通常用一维数组（或单个变量）存储中间结果。

=== 核心特征 ===  
1. '''最优子结构'''：问题的最优解包含子问题的最优解。  
2. '''重叠子问题'''：子问题被重复计算，可通过存储结果优化。  
3. '''状态转移方程'''：定义如何从子问题的解推导出当前问题的解。  

数学表示：  
<math>dp[i] = F(dp[i-1], dp[i-2], \ldots, dp[0])</math>  
其中，<math>dp[i]</math>表示状态<math>i</math>的解，<math>F</math>为状态转移函数。

== 经典问题示例 ==  

=== 斐波那契数列 ===  
**问题描述**：计算第<math>n</math>个斐波那契数（<math>F(0)=0</math>, <math>F(1)=1</math>, <math>F(n)=F(n-1)+F(n-2)</math>）。  

==== 递归解法（低效） ====  
<syntaxhighlight lang="python">  
def fibonacci(n):  
    if n <= 1:  
        return n  
    return fibonacci(n-1) + fibonacci(n-2)  
</syntaxhighlight>  
**缺点**：存在大量重复计算，时间复杂度为<math>O(2^n)</math>。  

==== 一维动态规划解法 ====  
使用数组存储已计算的结果：  
<syntaxhighlight lang="python">  
def fibonacci(n):  
    dp = [0] * (n + 1)  
    dp[0], dp[1] = 0, 1  
    for i in range(2, n + 1):  
        dp[i] = dp[i-1] + dp[i-2]  
    return dp[n]  
</syntaxhighlight>  
**优化**：时间复杂度<math>O(n)</math>，空间复杂度<math>O(n)</math>。  

==== 空间优化 ====  
仅需保存前两个状态：  
<syntaxhighlight lang="python">  
def fibonacci(n):  
    if n <= 1:  
        return n  
    prev, curr = 0, 1  
    for _ in range(2, n + 1):  
        prev, curr = curr, prev + curr  
    return curr  
</syntaxhighlight>  
**空间复杂度**降至<math>O(1)</math>。  

=== 爬楼梯问题 ===  
**问题描述**：每次可爬1或2阶台阶，求到达第<math>n</math>阶的方法数。  

==== 状态转移方程 ====  
<math>dp[i] = dp[i-1] + dp[i-2]</math>（与斐波那契数列相同）。  

==== 代码实现 ====  
<syntaxhighlight lang="python">  
def climb_stairs(n):  
    if n == 1:  
        return 1  
    dp = [0] * (n + 1)  
    dp[1], dp[2] = 1, 2  
    for i in range(3, n + 1):  
        dp[i] = dp[i-1] + dp[i-2]  
    return dp[n]  
</syntaxhighlight>  

== 实际应用案例 ==  

=== 最大子数组和（Kadane算法） ===  
**问题描述**：给定整数数组，找到连续子数组的最大和。  

==== 状态定义 ====  
<math>dp[i]</math>表示以第<math>i</math>个元素结尾的最大子数组和。  

==== 状态转移方程 ====  
<math>dp[i] = \max(nums[i], dp[i-1] + nums[i])</math>  

==== 代码实现 ====  
<syntaxhighlight lang="python">  
def max_subarray(nums):  
    dp = [0] * len(nums)  
    dp[0] = nums[0]  
    for i in range(1, len(nums)):  
        dp[i] = max(nums[i], dp[i-1] + nums[i])  
    return max(dp)  
</syntaxhighlight>  

**空间优化**：仅需维护当前最大值：  
<syntaxhighlight lang="python">  
def max_subarray(nums):  
    max_current = max_global = nums[0]  
    for num in nums[1:]:  
        max_current = max(num, max_current + num)  
        max_global = max(max_global, max_current)  
    return max_global  
</syntaxhighlight>  

== 总结 ==  
一维动态规划通过一维状态数组（或变量）存储子问题解，适用于状态转移仅依赖有限前驱状态的问题。关键步骤包括：  
1. 定义状态（如<math>dp[i]</math>）。  
2. 确定状态转移方程。  
3. 初始化边界条件。  
4. 选择空间优化策略（如滚动数组）。  

{{Collapse top|查看本章思维导图}}  
<mermaid>  
graph TD  
    A[一维动态规划] --> B[核心特征]  
    B --> B1[最优子结构]  
    B --> B2[重叠子问题]  
    B --> B3[状态转移方程]  
    A --> C[经典问题]  
    C --> C1[斐波那契数列]  
    C --> C2[爬楼梯问题]  
    A --> D[实际应用]  
    D --> D1[最大子数组和]  
</mermaid>  
{{Collapse bottom}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:动态规划]]