算法篇：动态规划(一)

灰子学技术

发布于 2020-10-30 14:43:11

2990

发布于 2020-10-30 14:43:11

文章被收录于专栏：灰子学技术灰子学技术

算法：

本篇是动态规划的第一篇文章，对于动态规划的题目，其实就是数学中的归纳法，最终需要找到一个公式，找到后面的值与前面数据之间的关联关系。

对于本次的几个题目来讲，公式比较简单：f(n+2) = f(n)+f(n-1)+X,详细内容需要参见每道题目的分析。

题目1: https://leetcode-cn.com/problems/climbing-stairs/

代码实现：

/* 动态规划典型题目：
   n=1, 只有1种走法
   n=2, 有两种走法，1+1和2
   n>2, 是n-1楼梯+1步和n-2楼梯+2步，这两种走法；走法是 f(n-1)+f(n-2)
*/
func climbStairs(n int) int {
    if n < 2 {
        return 1
    }
    res := make([]int,n)
    res[0] = 1
    res[1] = res[0]+1
    for i:=2;i<n;i++ {
       res[i] = res[i-1] + res[i-2]
    }
    return res[n-1]
}

执行结果：

题目2:

https://leetcode-cn.com/problems/min-cost-climbing-stairs/

代码实现：

// 公式：f(i) = f(i-1)+f(i-2)+cost[i]
func minCostClimbingStairs(cost []int) int {
     l := len(cost)
     if len(cost) < 2 {
         return 0
     }
     res := make([]int,l)
     // 0,1都是走1的的权重
     res[0] = cost[0]
     res[1] = cost[1]
     // 2以上的话，是n-1，n-2 最小值+最后一个位置的cost
     for i := 2; i< l; i++ {
         // 动态规划的公式
         res[i] = cost[i]+min(res[i-1],res[i-2])
     }
     return min(res[l-1],res[l-2])
}
func min(a,b int) int {
    if a>b {
        return b
    }
    return a
}

执行结果：

题目3:

https://leetcode-cn.com/problems/n-th-tribonacci-number/

代码实现：

// 公式：res[i]= res[i-1]+res[i-2]+res[i-3]
func tribonacci(n int) int {
    if n == 0 {
        return 0
    }
    if n ==1 || n==2{
        return 1
    }
    res := make([]int,n+1)
    res[0] = 0
    res[1] = 1
    res[2] = 1
    for i:=3;i<=n;i++ {
        res[i]= res[i-1]+res[i-2]+res[i-3]
    }
    return res[n]
}

执行结果：