746. 使用最小花费爬楼梯

爬楼梯，从右往左看，f(n) 表示从低 n 节开始时消耗的最少体力。

f(n) = 0，因为爬完了
f(n-1) = cost[n]，因为只能爬一节
f(n-2) = min(cost[n], cost[n-1])，因为可以爬一节/两节，可以选任意一个 cost
f(n) = cost[n] + min(f(n+1), f(n+2))，因为这节首先是要爬的，然后考虑爬一节还是爬两节，选 cost 最少的

1
impl Solution {
2
    pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
3
        // f(n) = cost[n] + min(f(n+1), f(n+2))
4
        let mut arr = vec![0; cost.len() + 1];
5
        arr[cost.len()] = 0;
6
        arr[cost.len() - 1] = cost[cost.len() - 1];
7
        arr[cost.len() - 2] = cost[cost.len() - 1].min(cost[cost.len() - 2]);
8

9
        for i in (0..(cost.len() - 1)).rev() {
10
            arr[i] = cost[i] + arr[i+1].min(arr[i+2]);
11
        }
12

13
        arr[0].min(arr[1])
14
    }
15
}

节省内存的话用三个变量就行，之后可以写一下。