【动态规划=递归+记忆化存储】跳台阶

求解代码

publicintjumpFloor(intnumber){int[]memo=newint[number+1];returndp(number,memo);}privateintdp(intnumber,int[]memo){if(number<=2){returnnumber;}if(memo[number]!=0){returnmemo[number];}memo[number]=dp(number-1,memo)+dp(number-2,memo);returnmemo[number];}

小贴士

1.要跳到第n级，最后一步只有两种可能：从n-1级跳1级上来、从n-2级跳2级上来，总方法数就是两者之和。

2.构建一个备忘录数组，用来缓存已经计算过的结果，数组下标对应台阶数，值对应该台阶的跳法数。

由于数组的默认值为0，0就表示该台阶的跳法数还未计算；

如果值≠0，就表示已经计算过，直接取值即可。