代码随想录算法训练营第三十八天丨动态规划理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

本文主要是介绍代码随想录算法训练营第三十八天丨动态规划理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划理论基础：

春节时候详细读了算法导论中的动态规划章节，结合书本和代码随想录网站做一个理论总结。

动态规划（Dynamic Programming, DP）是解决一类特定问题的算法思想，常用于求解最优化问题。动态规划的核心思想是将原问题拆解成一系列子问题，通过解决子问题，进而解决原问题。这种方法特别适用于那些具有重叠子问题和最优子结构性质的问题。动态规划关键在于掌握这两个概念：

重叠子问题：在求解过程中，相同的子问题会被多次求解。
最优子结构：一个问题的最优解包含其子问题的最优解。

动态规划通常用来解决两类问题：最优化问题和计数问题。最优化问题要求我们找到最好的解决方案，而计数问题要求我们找出满足某些条件的解的总数。

动态规划的基本步骤

动态规划解题通常遵循以下几个基本步骤：

定义状态（dp数组）：确定状态变量，这些变量通常是问题的参数，用于描述问题的各个阶段或者子问题。
确定状态转移方程（递推式）：找出状态之间的关系，即如何从一个或多个较小的子问题的解得到当前问题的解。
初始化状态（dp数组初始化）：确定初始条件，即最基本的子问题的解。
计算顺序：确定计算状态的顺序，有时可能需要按特定顺序进行，以确保在计算当前状态时，所需的所有子状态都已被计算。
解决问题：根据以上步骤解决问题，并根据需要找到最终解。

解题思路

动态规划的解题思路可以从以下几个方面入手：

问题拆解：识别问题是否可以分解为相似的子问题。
子问题重叠：检查子问题是否重叠，即是否有多个路径到达同一子问题，这是动态规划适用的关键。
备忘：为避免重复计算相同的子问题，可以通过备忘（使用数组或哈希表存储已解决的子问题的结果）来优化。
构建DP表：有时候可以构建一个表格（通常是二维或三维的），来系统地解决所有子问题，并保存它们的结果。
寻找边界条件：确定解决问题所需的最基本子问题（即边界条件）及其解，作为递推的基础。

509. 斐波那契数

练习DP的入门题，先练习动态规划的基本步骤：

class Solution:def fib(self, n: int) -> int:dp = [0] * (n + 1)if n > 0: dp[1] = 1for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]

由于当前状态只和前两个状态有关，可以优化空间复杂度：

class Solution:def fib(self, n: int) -> int:if n < 2:return nprev = 0cur = 1for i in range(1, n):prev, cur = cur, prev + curreturn cur

70. 爬楼梯

dp[0]没有意义，不需要初始化。

class Solution:def climbStairs(self, n: int) -> int:dp = [0] * (n + 1)if n < 4:return ndp[1], dp[2] = 1, 2for i in range(3, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]

class Solution:def climbStairs(self, n: int) -> int:if n < 4:return nprev, cur = 1, 2for _ in range(n - 2):prev, cur = cur, cur + prevreturn cur

746. 使用最小花费爬楼梯

支付费用后才能开始爬楼梯，楼顶在index=n的位置。

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:n  = len(cost)if n < 3:return min(cost)dp = [0] * (n + 1)for i in range(2, n + 1):dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1])return dp[n]

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:n  = len(cost)if n < 3:return min(cost)prev, cur =0, 0for i in range(2, n + 1):prev, cur = cur, min(prev + cost[i - 2], cur + cost[i - 1])return cur