代码随想录 day38 第九章动态规划part01

本文主要是介绍代码随想录 day38 第九章动态规划part01，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

● 理论基础

● 509. 斐波那契数

● 70. 爬楼梯

● 746. 使用最小花费爬楼梯

理论基础

解决动态规划必须要想清楚的点
1. dp数组以及下标的含义
2. 递推公式
3. dp数组如何初始化
4. 遍历顺序
5. 打印数组
  - 检查结果

1. 斐波那契数

关联 leetcode 509. 斐波那契数

思路
- 动规五部曲
  1. dp数组以及下标的含义
    1. dp[i] 就是第 i 个斐波那契数的值
  2. 递推公式
```
dp[i] = dp[i-1] + dp[i-2] 
```
  3. dp数组如何初始化
```
dp[0] = 0, dp[1] = 1
```
  4. 遍历顺序
    1. 从前往后遍历
  5. 打印数组
    1. debug 使用

题解

func fib(n int) int {if n < 2 {return n}dp := make([]int, n+1)dp[0] = 0dp[1] = 1for i := 2; i <= n; i++ {dp[i] = dp[i-1] + dp[i-2]}return dp[n]
}

2. 爬楼梯

关联 leetcode 70. 爬楼梯

求走到三阶有几种方法
- 不是求走到三阶要走几步
- 当前台阶只能从
  1. 当前阶的前一阶走一阶
  2. 当前阶的前二阶走二阶

思路

dp数组以及下标的含义

dp[i]： 爬到第i层楼梯，有dp[i]种方法

递推公式
```
dp[i] = dp[i-1] + dp[i-2] 
```

dp数组如何初始化

// 保证dp[1] 和 dp[2] 就好，dp[0]可以不用管
dp[1],dp[2] := 1,2

遍历顺序
1. 从前往后遍历
打印数组

题解

func climbStairs(n int) int {if n < 3 {return n}dp := make([]int, n+1)dp[0] = 0dp[1] = 1dp[2] = 2for i := 3; i <= n; i++ {dp[i] = dp[i-1] + dp[i-2]}return dp[n]
}

3. 使用最小花费爬楼梯

关联 leetcode 746. 使用最小花费爬楼梯

思路

顶楼是 cost 数组+1 的位置

dp数组以及下标的含义

dp[i] : 到达下标i的位置所需要的花费

递推公式

// 跳一步到达
dp[i] = dp[i-1] + cost[i-1]// 跳两步到达
dp[i] = dp[i-2] + cost[i-2]// 最小花费
dp[i] = min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2])

dp数组如何初始化

// 根据dp数组定义来的初始化
dp[0],dp[1] := 0,0

遍历顺序
1. 从前往后
打印数组

题解

func minCostClimbingStairs(cost []int) int {n := len(cost)//楼顶坐标dp := make([]int, len(cost)+1)dp[0], dp[1] = 0, 0for i := 2; i <= n; i++ {dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])}return dp[n]
}