代码随想录算法训练营第三十二天 | 509、70、746

算法
, , ,

509. 斐波那契数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package main

func fib(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }

    a, b := 0, 1
    for i := 2; i <= n; i++ {
        // 计算当前值 F(i) = F(i-1) + F(i-2)
        next := a + b
        // 更新前两个值
        a = b
        b = next
    }
    return b
}

70. 爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package main

func climbStairs(n int) int {
    if n <= 1 {
        return 1
    }
    a, b := 1, 1 // a: dp[0]=1, b: dp[1]=1
    for i := 2; i <= n; i++ {
        // 计算当前状态：dp[i] = dp[i-1] + dp[i-2]
        next := a + b
        // 更新前两个状态
        a = b
        b = next
    }
    return b
}

746. 使用最小花费爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    // 初始化前两个状态
    a, b := 0, 0

    // 从第 2 个阶梯开始计算到楼梯顶部
    for i := 2; i <= n; i++ {
        // 计算到达当前位置的最小花费
        next := min(a+cost[i-2], b+cost[i-1])
        // 更新状态
        a, b = b, next
    }
    return b
}

// 辅助函数：返回两个整数中的较小值
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}