网站建设公司fjfzwl百度知道个人中心
对于动态规划问题，将拆解为如下五步曲
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
509.斐波那契数
思路：
-
确定dp数组（dp table）以及下标的含义：dp[i]的定义为：第i个数的斐波那契数值是dp[i]
-
确定递推公式：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]
-
dp数组如何初始化：dp[0] = 0，dp[1] = 1
-
确定遍历顺序：从前到后遍历
-
举例推导dp数组：推导一下，当N为10的时候，dp数组应该是如下的数列：
0 1 1 2 3 5 8 13 21 34 55
class Solution:def fib(self, n: int) -> int:dp = [0 for _ in range(n+1)]if n < 1:return 0dp[0] = 0dp[1] = 1for i in range(2,n+1):dp[i] = dp[i-1] + dp[i-2]return dp[n]
70.爬楼梯
思路：
-
确定dp数组（dp table）以及下标的含义：dp[i]： 爬到第i层楼梯，有dp[i]种方法
-
确定递推公式：
dp[i] 可以有两个方向推出来。
首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
-
dp数组如何初始化：dp[0] = 1，dp[1] = 1
-
确定遍历顺序：从前到后遍历
-
举例推导dp数组：
class Solution:def climbStairs(self, n: int) -> int:dp = [0 for _ in range(n+1)]if n == 0:return 0dp[0] = 1dp[1] = 1for i in range(2,n+1):dp[i] = dp[i-1] + dp[i-2]return dp[n]
746.使用最小花费爬楼梯
思路：
-
确定dp数组（dp table）以及下标的含义：dp[i]爬到楼顶的花费
-
确定递推公式：
dp[i - 1]，到上i-1层楼梯，花费dp[i - 1]，i-1到i花费dp[i - 1]+cost[i-1]
dp[i - 2]，上i-2层楼梯，花费dp[i - 2]，i-2到i花费dp[i - 2]+cost[i-2]
dp [i] = min(dp[i - 1]+cost[i-1]，dp[i - 2]+cost[i-2])
-
dp数组如何初始化：dp[0] = 0，dp[1] = 0
**注意：**题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 从 到达 第 0 个台阶是不花费的，但从 第0 个台阶 往上跳的话，需要花费 cost[0]。
-
确定遍历顺序：从前到后遍历
-
举例推导dp数组：
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：
class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:n = len(cost) dp = [0 for _ in range(n+1)]if n < 1:return 0dp[0] = 0dp[1] = 0for i in range(2, n+1):dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])return dp[n]