分析步骤

  • 确定dp数组(dp table)以及下标的含义

  • 确定递推公式

  • dp数组如何初始化

  • 确定遍历顺序

  • 举例推导dp数组

———— 题解步骤来自博客

题目一

初识动归:b站一个魔性的up
leetcode:509

代码与解析

  • 确定dp数组(dp table)以及下标的含义
    dp用来记录每个斐波那契数
  • 确定递推公式
    题目中给了
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
  • dp数组如何初始化
    dp[0]=0
    dp[1]=1
  • 确定遍历顺序
    dp[i]是依赖 dp[i – 1] 和 dp[i – 2],那么遍历应该是从前往后遍历
  • 举例推导dp数组
eg: n=6
dp = [0,1,1,2,3,5,8]

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

题目二

leetcode:70

代码与解析

n=1  =>   1
n=2  =>   2:一次一步走两次, 一次两步
n=3  =>   3:(1,1,1)(1,2)(2,1)

当前状态可以由前两个状态倒出来
carl大佬在博客详细解释了

我理解的dp[0]是在地板上,不用动,地板即就是target
其余每一项的分析看上一题,代码很像

func climbStairs(n int) int {
    if n==1{
        return 1
    }
    dp:=make([]int,n+1)
    dp[1]=1
    dp[2]=2
    for i:=3;i<=n;i++{
        dp[i]=dp[i-1]+dp[i-2]
    }
    // fmt.Println(dp)
    return dp[n]
}
分类: 算法

站点统计

  • 文章总数:308 篇
  • 分类总数:19 个
  • 标签总数:190 个
  • 运行天数:950 天
  • 访问总数:33074 人次

浙公网安备33011302000604

辽ICP备20003309号