LeetCode | 图文详细描述动态规划DP算法及经典题型

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="htmledit_views">

本文将用简单直白的方式，从零开始带你掌握动态规划的精髓。你会发现：

  • 动态规划其实没那么难——它就是递归的“记性”版。
  • 状态转移方程不再玄学——从题目思路到实现，手把手教你推导。
  • 经典题型剖析——从“爬楼梯”到“背包问题”，全都有图、有代码、有思路。

看完这篇文章，动态规划不再是拦路虎，而是你刷题路上的好伙伴。现在，准备好解锁 DP 的魔法了吗？Let's go! 🎉

1.理论

1.1. 动态规划的定义

动态规划（Dynamic Programming, DP）是一种通过将问题分解为更小的子问题，逐步求解并存储中间结果，从而避免重复计算的优化方法。它适用于具有 重叠子问题 和 最优子结构 的问题。

1.2. 动态规划的关键特性

 1.2.1.重叠子问题（Overlapping Subproblems）

 问题可以分解为许多重复的子问题。例如：

斐波那契数列问题中：F(n) = F(n-1) + F(n-2)，子问题重复出现。

1.2.2.最优子结构（Optimal Substructure）

一个问题的最优解由其子问题的最优解构成。例如： 

爬楼梯问题：到达第 nnn 级的总方法数是第 n−1n-1n−1 和第 n−2n-2n−2 级方法数之和。 

1.2.3.状态转移方程（State Transition Equation）

描述如何从子问题的解构建更大问题的解，是动态规划的核心。例如： 

背包问题的状态转移方程：dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

1.3. 动态规划的常见步骤

1.3.1.定义状态（State）
用一个数组或矩阵 dp 表示问题的解，其中 dp[i] 或 dp[i][j] 表示问题在第 i或 (i,j) 状态的最优解。

1.3.2.状态转移方程（State Transition Equation）
找到子问题与原问题的递推关系，确定状态如何从前一个状态转移。

1.3.3.初始化（Initialization）
确定基础情况，例如：dp[0] 或 dp[0][0]。

1.3.4.递推计算（Iteration）
通过循环从基础状态逐步递推到目标状态。

1.3.5.返回结果（Result Extraction）
最终返回 dp[n] 或 dp[m][n] 等目标状态的值。

1.4. 动态规划的分类

1.4.1.一维动态规划

问题：斐波那契数列、爬楼梯、最小花费爬楼梯

特点：状态数组为一维，dp[i] 表示第 iii 步的解。

示例：爬楼梯 dp[i]=dp[i−1]+dp[i−2]

1.4.2.二维动态规划

问题：最短路径问题、背包问题、字符串匹配问题

特点：状态数组为二维矩阵，dp[i][j] 表示二维状态。

示例：最小路径和 dp[i][j]=grid[i][j]+min⁡(dp[i−1][j],dp[i][j−1])

1.4.3.区间动态规划

问题：矩阵链乘积、回文分割问题

特点：状态表示为区间，dp[i][j] 表示从第 iii 到第 jjj 的最优解。

示例：最长回文子序列 dp[i][j]=dp[i+1][j−1]+2if s[i]==s[j]dp[i][j] = dp[i+1][j-1] + 2 \quad \text{if } s[i] == s[j]dp[i][j]=dp[i+1][j−1]+2if s[i]==s[j]

1.4.4.背包动态规划

问题：01背包问题、完全背包问题

特点：根据背包容量和物品状态转移。

示例：01背包问题 dp[i][w]=max⁡(dp[i−1][w],dp[i−1][w−weight[i]]+value[i])

1.4.5.记忆化递归

问题：与普通动态规划类似，但通过递归解决，配合缓存（如字典或数组）存储中间结果。

特点：自顶向下的方式求解，与自底向上的普通 DP 思路相反。

1.5. 优化技巧

1.5.1.空间优化

如果状态转移只依赖前几步状态，可以通过滚动数组将空间复杂度从 O(n)O(n)O(n) 降低到 O(1)O(1)O(1)。

示例：斐波那契数列优化版本只用两个变量 prev2 和 prev1。

1.5.2.压缩维度

对于二维动态规划问题，可以压缩到一维数组进行状态存储。

示例：01 背包问题中，用一维数组存储容量状态。

1.5.3。减少不必要计算

通过提前剪枝，减少动态规划状态的计算范围。

总结：动态规划是一种递推式的优化算法，旨在以最少的计算解决递归性质的问题。

2.真题

2.0.基本

第 N 个斐波那契数

给定一个正整数 n，任务是找到第 n 个斐波那契数。

斐波那契数列是其中一项是前两项之和的序列。斐波那契数列的前两项是 0 后跟 1。斐波那契数列：0、1、1、2、3、5、8、13、21

斐波那契数定义：
  1. F(0)=0
  2. F(1)=1
  3. F(n)=F(n−1)+F(n−2)（当 n≥2）

例：

输入：n = 2
输出：1
说明：1 是斐波那契数列的第 2 个数字。

输入：n = 5
输出：5
说明：5 是斐波那契数列的第 5 个数字。

解题思路：

  1.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1">
class="hljs-ln-code"> class="hljs-ln-line">#方法1：递归，时间复杂度：O(2^n) 和 空间复杂度：O(n)
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="2">
    • class="hljs-ln-code"> class="hljs-ln-line">def nth_fibonacci(n):
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="3"> class="hljs-ln-code"> class="hljs-ln-line"># 函数 nth_fibonacci(n) 用于计算第 n 个斐波那契数。
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="4"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="5"> class="hljs-ln-code"> class="hljs-ln-line"> if n<=1:
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="6"> class="hljs-ln-code"> class="hljs-ln-line"> return n
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="7"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="8"> class="hljs-ln-code"> class="hljs-ln-line"> return nth_fibonacci(n-1)+nth_fibonacci(n-2)
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="9"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="10"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="11"> class="hljs-ln-code"> class="hljs-ln-line">n=5
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="12"> class="hljs-ln-code"> class="hljs-ln-line">result=nth_fibonacci(n)
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="13"> class="hljs-ln-code"> class="hljs-ln-line">print(result)
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="14"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="15"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="16"> class="hljs-ln-code"> class="hljs-ln-line">#方法2：自下而上的迭代法 就是计算斐波那契数的最优解法
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="17"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="18"> class="hljs-ln-code"> class="hljs-ln-line">def nth_fibonacci(n):
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="19"> class="hljs-ln-code"> class="hljs-ln-line"> if n<=1:
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="20"> class="hljs-ln-code"> class="hljs-ln-line"> return n
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="21"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="22"> class="hljs-ln-code"> class="hljs-ln-line"> prev2=0
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="23"> class="hljs-ln-code"> class="hljs-ln-line"> prev1=1
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="24"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="25"> class="hljs-ln-code"> class="hljs-ln-line"> for _ in range(2,n+1)：
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="26"> class="hljs-ln-code"> class="hljs-ln-line"> curr=prev1+prev2
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="27"> class="hljs-ln-code"> class="hljs-ln-line"> prev2=prev1
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="28"> class="hljs-ln-code"> class="hljs-ln-line"> prev1=curr
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="29"> class="hljs-ln-code"> class="hljs-ln-line"> return prev1
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="30"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="31"> class="hljs-ln-code"> class="hljs-ln-line">if __name__=="__main__"：
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="32"> class="hljs-ln-code"> class="hljs-ln-line"> n=5
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="33"> class="hljs-ln-code"> class="hljs-ln-line"> rusult=nth_fibonacci(n)
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="34"> class="hljs-ln-code"> class="hljs-ln-line"> print(n)
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="35"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="36"> class="hljs-ln-code"> class="hljs-ln-line">######## 方法最优性分析 ########
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="37"> class="hljs-ln-code"> class="hljs-ln-line">时间复杂度：O(n):只需一次从 2 到 n 的循环，每次循环进行常数操作。
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="38"> class="hljs-ln-code"> class="hljs-ln-line">空间复杂度：O(1):只用到了三个变量：prev2, prev1, 和 curr，不需要额外的数组存储所有结果。
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="39"> class="hljs-ln-code"> class="hljs-ln-line">优点
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="40"> class="hljs-ln-code"> class="hljs-ln-line">节省空间：将空间复杂度从O(n) 降低到 O(1)。
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="41"> class="hljs-ln-code"> class="hljs-ln-line">简洁高效：代码简洁明了，计算速度快。
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="42"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="43"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="44"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="45"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="46"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="47"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="48"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="49"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="50"> class="hljs-ln-code"> class="hljs-ln-line">#方法3：自上而下的方法 时间复杂度：O(n) 和 空间复杂度：O(n)
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="51"> class="hljs-ln-code"> class="hljs-ln-line">def nth_fibonacci(n):
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="52"> class="hljs-ln-code"> class="hljs-ln-line"> if n<=1:
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="53"> class="hljs-ln-code"> class="hljs-ln-line"> return n
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="54"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="55"> class="hljs-ln-code"> class="hljs-ln-line"> dp=[0]*(n+1)
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="56"> class="hljs-ln-code"> class="hljs-ln-line"> # 创建一个长度为n+1 的数组 dp，用来存储从 F(0) 到 F(n) 的结果。
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="57"> class="hljs-ln-code"> class="hljs-ln-line"> dp[0]=0
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="58"> class="hljs-ln-code"> class="hljs-ln-line"> dp[1]=1
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="59"> class="hljs-ln-code"> class="hljs-ln-line"> # 初始化已知的F(0)=0,F(1)=1
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="60"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="61"> class="hljs-ln-code"> class="hljs-ln-line"> for i in range(2,n+1):
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="62"> class="hljs-ln-code"> class="hljs-ln-line"> #遍历i从2到n
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="63"> class="hljs-ln-code"> class="hljs-ln-line"> dp[i]=dp[i-1]+dp[i-2]
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="64"> class="hljs-ln-code"> class="hljs-ln-line"> return dp[n]
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="65"> class="hljs-ln-code"> class="hljs-ln-line"> #每次迭代都将迭代结果存储到dp[i]中，避免重复计算。
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="66"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="67"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="68"> class="hljs-ln-code"> class="hljs-ln-line">if __name__=="__main__":
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="69"> class="hljs-ln-code"> class="hljs-ln-line"> n=5
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="70"> class="hljs-ln-code"> class="hljs-ln-line"> result=nth_fibonacci(n)
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="71"> class="hljs-ln-code"> class="hljs-ln-line"> print(result)
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="72"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="73"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="74"> class="hljs-ln-code"> class="hljs-ln-line">#动态规划方法通过迭代计算，只需遍历一次从 2 到 n 的范围，每次计算都只涉及常数操作，因此时间复杂度是 O(n)。
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="75"> class="hljs-ln-code"> class="hljs-ln-line">
  • class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="76"> class="hljs-ln-code"> class="hljs-ln-line">#使用了一个大小为n+1 的数组 dp 来存储中间计算结果，占用线性空间。
    •  class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}" onclick="hljs.signin(event)">

    需掌握题型

    2.1.简单

    【Leetcode70】爬楼梯 Climbing Stairs

     定义问题：有 n 级楼梯，每次可以走 1 步或 2 步，求到达顶楼的总方法数。

    1.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1"> class="hljs-ln-code"> class="hljs-ln-line">def climb_stairs_optimized(n):
    2.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="2"> class="hljs-ln-code"> class="hljs-ln-line">    if n<=1:
    3.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="3"> class="hljs-ln-code"> class="hljs-ln-line">        return 1
    4.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="4"> class="hljs-ln-code"> class="hljs-ln-line">    
    5.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="5"> class="hljs-ln-code"> class="hljs-ln-line">    #初始化两个变量，用来存储最近两次计算结果
    6.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="6"> class="hljs-ln-code"> class="hljs-ln-line">    prev2=1 #代表 f(n−2)，初始值为 1
    7.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="7"> class="hljs-ln-code"> class="hljs-ln-line">    prev1=1 代表 f(n−1)，初始值为 1
    8.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="8"> class="hljs-ln-code"> class="hljs-ln-line"> 
    9.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="9"> class="hljs-ln-code"> class="hljs-ln-line"> 
    10.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="10"> class="hljs-ln-code"> class="hljs-ln-line">    #迭代计算斐波那契数列
    11.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="11"> class="hljs-ln-code"> class="hljs-ln-line">    for _ in range(2,n+1):  #使用一个循环，从第 2 阶楼梯计算到第n阶楼梯
    12.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="12"> class="hljs-ln-code"> class="hljs-ln-line"> 
    13.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="13"> class="hljs-ln-code"> class="hljs-ln-line">        curr=prev1+prev2 #当前楼梯的方法数，由前两阶的和决定 
    14.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="14"> class="hljs-ln-code"> class="hljs-ln-line"> 
    15.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="15"> class="hljs-ln-code"> class="hljs-ln-line">        prev2=prev1 #将 prev1（即 f(n−1)）赋值给 prev2
    16.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="16"> class="hljs-ln-code"> class="hljs-ln-line"> 
    17.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="17"> class="hljs-ln-code"> class="hljs-ln-line">        prev1=curr  # 将 curr（即 f(n)）赋值给 prev1。 这样 prev1 和 prev2 始终保存最近的两次计算结果。
    18.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="18"> class="hljs-ln-code"> class="hljs-ln-line"> 
    19.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="19"> class="hljs-ln-code"> class="hljs-ln-line">    return prev1 #循环结束时，prev1 存储的是 f(n)，即到达第 n 阶的方法数。
    20.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="20"> class="hljs-ln-code"> class="hljs-ln-line"> 
    21.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="21"> class="hljs-ln-code"> class="hljs-ln-line"> 
    22.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="22"> class="hljs-ln-code"> class="hljs-ln-line">if __name__="__main__":
    23.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="23"> class="hljs-ln-code"> class="hljs-ln-line">    n=5
    24.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="24"> class="hljs-ln-code"> class="hljs-ln-line">    print("ways to climb stairs:", climb_stairs_optimized)
     class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}" onclick="hljs.signin(event)">

    运行过程：

    假设 n=5，步骤如下：

    class="table-box">
    Iterationprev2 (f(n−2))prev1 (f(n−1))curr (f(n))
    初始值01-
    n=2n=2n=2111
    n=3n=3n=3122
    n=4n=4n=4233
    n=5n=5n=5355

    最终，prev1 = 5，表示爬到第 5 阶的方法数为 5。

    时间与空间复杂度分析

    时间复杂度：O(n)

    空间复杂度：

    1. 使用数组 O(n)：需要额外数组存储中间结果。
    2. 空间优化 O(1)：仅存储两个变量，节省了内存。

    2.2.中等

    【Leetcode53】最大子数组(Maximum Subarray)

    问题：给定一个整数数组，找到nums子数组，并返回其总和

    1.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1"> class="hljs-ln-code"> class="hljs-ln-line">def max_subarray(nums):
    2.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="2"> class="hljs-ln-code"> class="hljs-ln-line">    current_sum=max_sum=nums[0] # 初始化 current_sum 和 max_sum 为数组的第一个元素
    3.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="3"> class="hljs-ln-code"> class="hljs-ln-line">    # 第一个元素已经处理过
    4.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="4"> class="hljs-ln-code"> class="hljs-ln-line"> 
    5.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="5"> class="hljs-ln-code"> class="hljs-ln-line">    for i in range(1,len(nums)): # 从第二个元素开始遍历
    6.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="6"> class="hljs-ln-code"> class="hljs-ln-line">    
    7.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="7"> class="hljs-ln-code"> class="hljs-ln-line">        current_sum=max(nums[i],current_sum+nums[i]) # 当前子数组的最大和
    8.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="8"> class="hljs-ln-code"> class="hljs-ln-line">    
    9.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="9"> class="hljs-ln-code"> class="hljs-ln-line">        max_sum=max(max_sum,current_sum) # 更新全局最大和
    10.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="10"> class="hljs-ln-code"> class="hljs-ln-line"> 
    11.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="11"> class="hljs-ln-code"> class="hljs-ln-line">    return max_sum
    12.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="12"> class="hljs-ln-code"> class="hljs-ln-line"> 
    13.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="13"> class="hljs-ln-code"> class="hljs-ln-line">if __name__=="__main__":
    14.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="14"> class="hljs-ln-code"> class="hljs-ln-line">    nums=[-2,1,-3,4,-1,2,1,-5,4]
    15.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="15"> class="hljs-ln-code"> class="hljs-ln-line">    print("最大子数组和：",max_subarray(nums))
     class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}" onclick="hljs.signin(event)">

     运行过程：

    数组：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

    class="table-box">
    元素current_sum 更新规则current_summax_sum
    -2初始值-2-2
    1max(1, -2 + 1) = 111
    -3max(-3, 1 - 3) = -2-21
    4max(4, -2 + 4) = 444
    -1max(-1, 4 - 1) = 334
    2max(2, 3 + 2) = 555
    1max(1, 5 + 1) = 666
    -5max(-5, 6 - 5) = 116
    4max(4, 1 + 4) = 556

     最优性分析：

    【Leetcode64】网格中的最小路径/最小路径总和（Minimux Path Sum）

    给定一个2d矩阵成本[][]，任务是计算从（0， 0）到（m，n）的最小成本路径。矩阵的每个像元都表示求解该像元的成本。到达路径的总费用（米，N）是该路径（包括源和目标）上所有费用的总和。我们只能从给定的单元格依次、向右和对角线依次遍历单元格，即从给定的单元格开始单元格 （i，j）、单元格（i+1，j）、（i，j+1）和（i+1，j+1）可以遍历。

    问题分析：

    要找到从左上角 (0, 0) 到右下角 (m, n) 的最小成本路径，可以使用 动态规划。动态规划是一种有效的方法，它通过记录每一步的最优结果，避免了重复计算。

    动态规划的最优解

    我们定义一个辅助的动态规划矩阵 dp，其中 dp[i][j] 表示从 (0, 0) 到 (i, j) 的最小成本路径。转移方程如下：

    dp[i][j]=cost[i][j]+min⁡(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])

    1.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1"> class="hljs-ln-code"> class="hljs-ln-line">def min_cost_path(cost,m,n):
    2.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="2"> class="hljs-ln-code"> class="hljs-ln-line">    rows=len(cost)
    3.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="3"> class="hljs-ln-code"> class="hljs-ln-line">    cols=len(cost[0])
    4.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="4"> class="hljs-ln-code"> class="hljs-ln-line">    
    5.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="5"> class="hljs-ln-code"> class="hljs-ln-line">    # 创建动态规划矩阵
    6.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="6"> class="hljs-ln-code"> class="hljs-ln-line">    dp=[[0]*clos for _ in range(rows)]
    7.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="7"> class="hljs-ln-code"> class="hljs-ln-line"> 
    8.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="8"> class="hljs-ln-code"> class="hljs-ln-line">    # 初始化起点
    9.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="9"> class="hljs-ln-code"> class="hljs-ln-line">    dp[0][0]=cost[0][0]
    10.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="10"> class="hljs-ln-code"> class="hljs-ln-line"> 
    11.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="11"> class="hljs-ln-code"> class="hljs-ln-line">    # 初始化第一行
    12.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="12"> class="hljs-ln-code"> class="hljs-ln-line">    for j in range(1,cols):
    13.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="13"> class="hljs-ln-code"> class="hljs-ln-line">        dp[0][j]=dp[0][j-1]+cost[0][j]
    14.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="14"> class="hljs-ln-code"> class="hljs-ln-line">    
    15.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="15"> class="hljs-ln-code"> class="hljs-ln-line">    # 初始化第一列
    16.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="16"> class="hljs-ln-code"> class="hljs-ln-line">    for i in range(1,rows):
    17.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="17"> class="hljs-ln-code"> class="hljs-ln-line">        dp[i][0]=dp[i-1][0]+cost[i][0]
    18.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="18"> class="hljs-ln-code"> class="hljs-ln-line"> 
    19.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="19"> class="hljs-ln-code"> class="hljs-ln-line">    
    20.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="20"> class="hljs-ln-code"> class="hljs-ln-line">    # 填充剩余的 dp 矩阵
    21.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="21"> class="hljs-ln-code"> class="hljs-ln-line">    for i in range(1,rows):
    22.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="22"> class="hljs-ln-code"> class="hljs-ln-line">        for j in range(1,cols):
    23.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="23"> class="hljs-ln-code"> class="hljs-ln-line">        dp[i][j]=cost[i][j]+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
    24.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="24"> class="hljs-ln-code"> class="hljs-ln-line"> 
    25.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="25"> class="hljs-ln-code"> class="hljs-ln-line">    # 返回右下角的最小成本路径
    26.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="26"> class="hljs-ln-code"> class="hljs-ln-line">    return dp[m][n]
    27.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="27"> class="hljs-ln-code"> class="hljs-ln-line"> 
    28.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="28"> class="hljs-ln-code"> class="hljs-ln-line">if __name__ == "__main__":
    29.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="29"> class="hljs-ln-code"> class="hljs-ln-line">    cost = [
    30.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="30"> class="hljs-ln-code"> class="hljs-ln-line">        [1, 2, 3],
    31.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="31"> class="hljs-ln-code"> class="hljs-ln-line">        [4, 8, 2],
    32.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="32"> class="hljs-ln-code"> class="hljs-ln-line">        [1, 5, 3]
    33.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="33"> class="hljs-ln-code"> class="hljs-ln-line">    ]
    34.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="34"> class="hljs-ln-code"> class="hljs-ln-line">    m, n = 2, 2  # 目标位置
    35.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="35"> class="hljs-ln-code"> class="hljs-ln-line">    result = min_cost_path(cost, m, n)
    36.  class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="36"> class="hljs-ln-code"> class="hljs-ln-line">    print("Minimum cost path:", result)
     class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}" onclick="hljs.signin(event)">

    最优性分析：

    时间复杂度：O(m×n)

    空间复杂度：O(m×n)

    参考文献

    [1]A Beginner's Guide to Dynamic Programming

    [2]Dynamic Programming or DP - GeeksforGeeks

    注：本文转载自blog.csdn.net的夏天｜여름이다的文章"https://blog.csdn.net/weixin_44649780/article/details/145140378"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
    复制链接
    复制链接
    相关推荐
    发表评论

    评论记录：

    未查询到任何数据！