本文主要是介绍算法训练营day33(补)，动态规划1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// 509. 斐波那契数
func fib(n int) int {
if n < 2 {
return n
}
return fib(n-1) + fib(n-2)
}
// 70. 爬楼梯, 本质上就是斐波那契数列但是用递归法，力扣提交会超时
func climbStairs(n int) int {
if n <= 2 {
return n
}
a, b, sum := 1, 2, 0
for i := 1; i < n; i++ {
sum = a + b
a = b
b = sum
}
return sum
}
// 746. 使用最小花费爬楼梯
func minCostClimbingStairs(cost []int) int {
//最高值是 len(cost) + 1
n := len(cost) + 1
dp := make([]int, n)
//可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯, 那么初始值0,1都赋值为零
dp[0] = 0
dp[1] = 0
for i := 2; i < n; i++ {
//因为求最小花费，dp[i]取前1个与前2个的最小值
if dp[i-1]+cost[i-1] < dp[i-2]+cost[i-2] {
dp[i] = dp[i-1] + cost[i-1]
} else {
dp[i] = dp[i-2] + cost[i-2]
}
}
return dp[n-1]
}
这篇关于算法训练营day33(补)，动态规划1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
