好久没做 DP 了,基本思路就是记录之前状态,然后通过之前的状态推导得出下一个状态的方程(状态转移方程)。
impl Solution { pub fn climb_stairs(n: i32) -> i32 { // 1 1 // 2 // f(2) = 2 // // 1 1 1 // 1 2 // 2 1 // f(3) = 2 * f(1) + 1 // // 1 1 1 1 // 1 1 2 // 1 2 1 // 2 1 1 // 2 2 // f(4) = f(3) + f(2); // // f(5) = f(4) + f(3); // // f(n) = 1 f(n-1) // 2 f(n-2)
if n == 1 { return 1; } else if n == 2 { return 2; }
let mut data = vec![1, 2]; let mut next = 0;
let mut i = 2; while i < n { data[next] = data[0] + data[1]; i += 1; if i == n { return data[next]; }
if next == 0 { next = 1; } else { next = 0; } } data[next] }}