LeetCode-70 爬楼梯

题目描述：

思路想法：

这道题，用递归无疑是最不费脑子的。

假设现有 10个台阶，我最后可以走1步，也可以走2步；走1步的话递归9个台阶；走两步递归8个台阶；

但是提交发现超时了。

这个时候当然是动态规划的阉割版啦；

用hash表保存下记录嘛，省的每次都傻乎乎的去递归；

Java 代码：

class Solution { public int climbStairs(int n) { HashMap memery = new HashMap(); return recursive(n, memery); } public int recursive(int x,HashMap memery){ if (x==1) return 1; if(x==2) return 2; String t = String.valueOf(x); Object value = memery.get(t); if(value!=null){return (int) value;} int ans = recursive(x-1,memery)+recursive(x-2,memery); memery.put(t,ans); return ans; } }

核心技能：

明白递归和动态规划的联系，知道怎么用hash表保存数据，知道常见递归减小问题的规模的办法。