代码随想录 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. 当前阶的前二阶 走二阶

• 思路

  1. dp数组以及下标的含义

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

  2. 递推公式

     dp[i] = dp[i-1] + dp[i-2] 
     

  3. dp数组如何初始化

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

  4. 遍历顺序

     1. 从前往后遍历

  5. 打印数组

• 题解

  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 的位置

  1. dp数组以及下标的含义

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

  2. 递推公式

     // 跳一步到达
     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])
     

  3. dp数组如何初始化

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

  4. 遍历顺序

     1. 从前往后

  5. 打印数组

• 题解

  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]
  }
  

4.题外话

• 爬楼梯
  • 方案是固定的不要重复计算
    • 从少一级的楼梯往上爬：还需要爬一步 —》唯一的一种方案
    • 从少两级的楼梯往上爬：还需要两步 —》唯一的一种方案

这篇关于代码随想录 day38 第九章 动态规划part01的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---