当时的我根本不知道动态规划的相关概念，什么状态，什么转移方程，通通没听过。
没错，当时就那么菜！
二话不说，直接使用暴力解法。
class Solution {
public int climbStairs(int n) {
return calcWays(n);
}
private int calcWays( int n ){
if ( n == 1) return 1;
if ( n == 2) return 2;
return calcWays(n-1) + calcWays(n-2);
}
}
很明显，无脑的递归暴力解法包含了大量的重复计算，提交上去直接标红提示超出时间限制。
后来看了网上高票答案的分析，知道了备忘录的概念，于是很容易写出优化后的代码。
//采用备忘录的方式来存子问题的解以避免大量的重复计算
class Solution {
int[] memo;
public int climbStairs(int n) {
memo = new int[n+1];
return calcWays(n);
}
private int calcWays( int n ){
if ( n == 1) return 1;
if ( n == 2) return 2;
if (memo[n] == 0)
memo[n] = calcWays(n-1) + calcWays(n-2);
return memo[n];
}
}
再后来，发现备忘录是自顶向下的方式，稍许变动，修改为自低向上的递推方式就是动态规划的形式。
class Solution {
public int climbStairs(int n) {
int[] memo = new int[n+1];
memo[0] = 1;
memo[1] = 1;
for(int i = 2 ; i <= n; i++){
memo[i] = memo[i-1] + memo[i-2];
}
return memo[n];
}
}
按照这样的刷题路径下来，发现对这类题型有了初步的思考途径，有了发力点，再也不会一筹莫展：看题懵逼半小时，Coding 只会按空格。
彻底搞懂这题后，就需要找到类似的题型，然后不断的重复练习：最小路径和、整数拆分、完全平方数、解码方法、不同路径、不同路径 II。
通过这些练习，寻找题目中的共同点，为什么这类题型都可以这样思考呢？
慢慢的，知道了最优子结构、状态转移方程、重叠子问题的概念，不知不觉动态规划的知识点已经掌握了 80%。
再遇到更高难度的动态规划的题目时，心里也明白，一时半会没做成无法就是最优子结构、状态转移方程、重叠子问题没有理清楚。
这样长期坚持下来，接触新的题型时也可以从容不迫的思考。
Uoffer也为留学生准备了更为全面的CS刷题班，帮助北美留学生通过一系列刷题成功拿到大厂offer。
