[代码随想录]Day33-动态规划part01

题目：509. 斐波那契数

思路：

动规五部曲：
这里我们要用一个一维dp数组来保存递归的结果

1. 确定dp数组以及下标的含义
   dp[i]的定义为：第i个数的斐波那契数值是dp[i]

2. 确定递推公式
   为什么这是一道非常简单的入门题目呢？
   因为题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

3. dp数组如何初始化
   题目中把如何初始化也直接给我们了，如下：
   dp[0] = 0;
   dp[1] = 1;

4. 确定遍历顺序
   从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

5. 举例推导dp数组
   按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：
   0 1 1 2 3 5 8 13 21 34 55
   如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

代码1：

动态规划

func fib(n int) int {
    if n < 2 {
        return n
    }
    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]
} 

代码2：

滚动数组

func fib(n int) int {
    if n == 0 {
        return 0
    } 
    if n == 1 {
        return 1
    }
    a,b,c := 0, 1, 1
    for i := 2; i < n; i++ {
        a = b
        b = c
        c = a + b
    }
    return c
}

参考：

代码随想录

题目：70. 爬楼梯

思路：

思路其实和上面一样，比如走到3层的方法数dp[3] ->其实就是 dp[1] 走2步，dp[2] 走1步，即dp[n] = dp[n-1] + dp[n-2]

代码：

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]
    }
    return dp[n]
}

参考：

代码随想录

题目：746. 使用最小花费爬楼梯

思路：

和上面思路差不多，每一步都需要选前两步最小的即可。

代码：

func minCostClimbingStairs(cost []int) int {
    lens := len(cost)
    dp := make([]int,lens)
    dp[0] = cost[0]
    dp[1] = cost[1]
    for i := 2; i < lens; i++ {
        dp[i] = cost[i] + min(dp[i-1], dp[i-2])
    }
    return min(dp[lens-1], dp[lens-2])
}
func min(a,b int) int {
    if a < b {
        return a
    }
    return b
}

参考：

代码随想录