Java教程

刷题Day19-动态规划(1)

本文主要是介绍刷题Day19-动态规划(1),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

509. 斐波那契数

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

70. 爬楼梯

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

746. 使用最小花费爬楼梯

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

 

这篇关于刷题Day19-动态规划(1)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!