题解 | #跳台阶扩展问题#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    int jumpFloorII(int number) {
        // write code here
        int dp = 1;
        int pre_sum = 0;
        int tmp = dp;
        for(int i = 1 ; i < number ; i += 1){
            tmp = dp;
            dp = dp + 1 + pre_sum;
            pre_sum += tmp;
        }
        return dp;
    }
};

题解：使用动态规划，动规四部曲：1）确定dp数组，在第i级台阶有dp[i]种跳法；也可以使用滚动数字，思路是使用两个变量，一个变量为dp，负责记录当前的dp值，一个负责记录当前i - 1前的dp累加和。2）递推公式：dp = pre_sum + dp + 1。也就是每跳上第i级台阶，可以从第0级台阶到第i - 1级台阶跳到第i级台阶。所以就可以用 pre_sum(i - 1级台阶前的dp累加和) + dp + 1。3）初始化：dp = 1,pre_sum = 0; 4）遍历顺序：从头到尾。时间复杂度是O(n)，空间复杂的是O(1)。