走楼梯——走楼梯（一）

在介绍动态规划的核心思想前，先看一道题。

LeetCode_70_ClimbingStairs

题目分析：

令dp[i]代表有多少种方法可到达第i层，
由于第i层只能由i-1走一层或者i-2走两层达到，
故可得dp[i] = dp[i-2] + dp[i-1]，
很明显根据题意dp[1] = 1,dp[2] = 2。
dp[0]哪去了？为了我们写起来好看，浪费掉了。
如果喜欢你也可以用dp[0] = 1, dp[1] = 2,只是最后结果是dp[i-1]而不是dp[i]就是了。

解法一：递归

public static int climbStairs_recursion(int n){
    if(1 == n)
        return 1;
    else if(2 == n)
        return 2;
    return climbStairs_recursion(n-2) + climbStairs_recursion(n-1);
}

解法一分析

  解法一存在一个问题，
  因为dp[i] = dp[i-2] + dp[i-1]，则dp[i-1] = dp[i-3] + dp[i-2]，
  此刻dp[i-2]重复出现了两次。
  关键就在这里，这个重复的dp[i-2]并非重复一次这么简单，
  因为dp[i-2]又是由dp[i-4]+dp[i-3]得到，层层递归下去，将是2^(i-2)次函数调用，
  举一个例子，当i=30时候，dp[i]将会调用函数1664079次！

解法二：递归-动态规划

public static int climbStairs_dp_recursion(int n, int[] dp){
    if(1 == n)
        return 1;
    else if(2 == n)
        return 2;
    if(0 == dp[n])
        dp[n] = climbStairs_dp_recursion(n-2, dp) + climbStairs_dp_recursion(n-1, dp);
    return dp[n];
}

解法二分析

  1.使用一个数组来缓存了中间结果，防止了“重叠子问题”的重复计算。

  2.解法二依然存在一个问题，就是在于“递归”这种写法，递归产生的函数调用将消耗线程栈内存。
    使用-Xss180k作为虚拟机启动参数将线程栈设置为180k（jvm允许的最小值），
    并将问题规模n设置为3000，就会出现Stack Over flow。

解法三：循环-动态规划

public static int climbStairs_dp_loop(int n){
    if(1 == n)
        return 1;
    else if(2 == n)
        return 2;

    int[] dp = new int[n+1];
    int res = 0;
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i < n+1; i++) {
        res = dp[i] = dp[i-2] + dp[i-1];
    }
    return res;
}

解法三分析

1.解决方法是改为循环，
  因为递归和循环永远可以相互转换，请不要怀疑“永远”这个词的严谨性。

2.最后还有一个可优化的点，内存使用。
  我们使用dp[i] = dp[i-2] + dp[i-1]这个式子，循环递推出结果，
  dp[i]使我们想要的结果，而只需要dp[i-2]和dp[i-1]得到，
  然而我们却保留了i个也就是所有递推过程的中间结果，显然这是一种浪费。

解法四：循环-动态规划-内存优化

public static int climbStairs_dp_loop_lessMemory(int n){
    if(1 == n)
        return 1;
    else if(2 == n)
        return 2;

    int res = 0;
    int temp1 = 1;
    int temp2 = 2;
    for (int i = 3; i < n+1; i++) {
        res = temp1 + temp2;
        temp1 = temp2;
        temp2 = res;
    }
    return res;
}

解法四分析

通过两个变量的交替更新使用，达到了节约内存的目的，
这种不断更新两个变量的做法，就像将整个数组“滚动”起来了一样，在动态规划中称为“滚动数组”。
这里不用担心我们丢掉的结果，因为题目只求最后的值。

总结

1.将结果集合之间的关系描述为“动态转换方程”。
动态规划的所有核心都在这一步。
在做dp时，
不要关注数据和最终结果的关系。
关注结果集合之间的关系！
结果集合指什么，此题中所有dp[i]的值的集合就是结果集合。
我们找到的dp[i] = dp[i-2] + dp[i-1]，就是结果集合之间的关系。
这个关系就是"动态转换方程"。
2.构造递推初始项。
3.缓存推导过程中的“重叠子问题”，防止重复计算。
4."滚动使用变量或数组"是常见的dp内存优化方式。

相应例题的 Github