代码随想录day32 || 509 斐波那契数列，70 爬楼梯，746 最小代价爬楼梯

509 斐波那契数列

func fib(n int) int {
	// dp五部曲
	// 1 dp数组含义以及下标含义: 本题保存的是完整的斐波那契数列，i 对应数列的第i个数字
	// 2 递推公式: F(n) = F(n - 1) + F(n - 2)
	// 3 dp数组初始化: 由递推公式推到，0， 1 两位需要手动赋值，否则，oor
	// 4 遍历顺序: 求第n个数字，需要将数列遍历创建到第n个位置
	// 5 打印dp数组 
	
	var resli = []int{0, 1}
	for i := 2; i <= n; i++ {
		resli = append(resli, resli[i-1] + resli[i-2])
	}
	return resli[n]
}

70 爬楼梯

func climbStairs(n int) int {
	// dp五部曲
	// 确定dp数组以及下标含义： dp存储当前已经爬的阶梯数
	// 递推公式： f(n) = f(n - 1) + f(n - 2) // 即本次爬两步需要的方法 + 本次爬一步需要的方法总数
	// dp数组初始化： f(0) = 0, f(1) = 1
	// 遍历顺序： 从前往后
	// 打印dp

	var res = []int{0, 1, 2}
	for i := 3; i<=n; i++ {
		res = append(res, res[i-1] + res[i-2])
	}
	return res[n]
}

746 最小代价爬楼梯

func minCostClimbingStairs(cost []int) int {
	// dp数组以及下标含义： dp保存了爬到i楼累计最小体力消耗
	// 递推公式： mc(k) = min(mc[k-1] + cost[k-1], mc[k-2]+cost[k-2]), 从k-1消耗体力爬一层 或者 从k-2消耗体力爬两层
	// dp初始化： 题目给出了0，1两层都可以作为起点，所以0-1需要最小体力和都是0
	// 遍历顺序： 从前往后
	// 打印dp

	var mincost = []int{0, 0}
	for i := 2; i <= len(cost); i++ {
		mincost = append(mincost, min(cost[i-1] + mincost[i-1], cost[i-2] + mincost[i-2]))
	}
	fmt.Println(mincost)
	return mincost[len(cost)]
}

func min (x, y int )int {
	if x < y {
		return x
	}
	return y
}