爬楼梯

• 这是我比较喜欢的动态规划的题目
• 爬楼梯

递归算法

• 我们用非常愚蠢的办法解决这个问题，假设我们有一个楼梯，楼梯有 n 级台阶，每次可以上 1 级或者 2 级台阶，问有多少种不同的上楼方式。
• 每次我们可以走两步 也可以走一步，也就是说在这一级台阶，有两种可能性。
• 但是因为从第一级台阶往上走这个思路很不好递推，所以我们倒过来往下走
• 也就是说我们从第 n 级台阶往下走，走到第 n-1 级台阶或者 n-2 级台阶。

//n 为当前台阶数
fn process(n:i32)->i32{
    if n==0{
        return 1;
    }else  if n==1{
        return 1; 
    }else{
        return process(n-1)+process(n-2);
    }
}

• 好了这道题就解答完了，我擦勒为社么报错了？

• 这个错误是因为递归涉及到了太多的重复计算，比如说我们在计算第 5 级台阶的时候，我们需要计算第 4 级台阶和第 3 级台阶， 而在计算第 4 级台阶的时候，我们又需要计算第 3 级台阶和第 2 级台阶，这样就会导致重复计算。

记忆化搜索优化

• 我们可以用一个数组来记录已经计算过的结果，每次计算时优先查询这样就可以避免重复计算。

fn process(n:i32,arr:&mut Vec<i32>)->i32{
    if arr[n as usize]!=0{
        return arr[n as usize];
    }
  return match n{
        0=>arr[n as usize]=>1,
        1=>arr[n as usize]=>1,
        _=>arr[n as usize]=>{
           let res=process(n-1,arr)+process(n-2,arr);
           arr[n as usize]=res;
           res
        },
    }
}

隐藏boss动态规划

• 虽然记忆化搜素已经优化了很多，但是我们还是可以继续优化。
• 动态规划是什么呢？动态规划是从递归的过程中寻找规律，然后按照规律去计算出结果
• 所以这道题该怎么改为动态规划呢？

• 先看代码 通过递归我们可以寻找到规律 第一级台阶有 1 种走法，第二级台阶有 2 种走法， 第三级台阶的走法是第一级台阶和第二级台阶的走法之和，第四级台阶的走法是第二级台阶和第三级台阶的走法之和。
• 也就是说第 n 级台阶的走法是第 n-1 级台阶和第 n-2 级台阶的走法之和。
• 所以我们可以用一个数组来记录每一级台阶的走法，然后从第 3 级台阶开始计算，直到第 n 级台阶。 即 f(n)=f(n-1)+f(n-2) 就可以得到上面的代码了