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

跳台阶扩展问题

https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    int jumpFloorII(int number) {
        /**
         * f(n)   = f(n-1) + f(n-2) + f(n-3) + ... + f(1) + f(0)
         * f(n-1) =          f(n-2) + f(n-3) + ... + f(1) + f(0)
         * f(n-2) =                   f(n-3) + ... + f(1) + f(0)
         * ------------------------------------------------------
         * f(n)   = [        f(n-2) + f(n-3) + ... + f(1) + f(0)] + // f(n-1)
         *                 + f(n-2) + f(n-3) + ... + f(1) + f(0)
         *        = 2 * [    f(n-2) + f(n-3) + ... + f(1) + f(0)]
         *        = 2 * f(n-2)
         * ------- 归纳 --------------------
         * f(n) = 2 * f(n-1)
         */
        vector<int> dp(number + 1);

        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= number; ++i) {
            dp[i] = 2 * dp[i - 1];
        }
        return dp[number];
    }
};

这里还是得做归纳:

  1. 第 n 阶 的台阶数量等于 前n-1 阶方法的总和 + 1 --》 f(n) = f(n-1) + f(n-2) + ... f(2) + f(1) + 1
  2. 将 1 记为 f(0)

/**
         * f(n)   = f(n-1) + f(n-2) + f(n-3) + ... + f(1) + f(0)
         * f(n-1) =          f(n-2) + f(n-3) + ... + f(1) + f(0)
         * f(n-2) =                   f(n-3) + ... + f(1) + f(0)
         * ------------------------------------------------------
         * f(n)   = [        f(n-2) + f(n-3) + ... + f(1) + f(0)] + // f(n-1)
         *                 + f(n-2) + f(n-3) + ... + f(1) + f(0)
         *        = 2 * [    f(n-2) + f(n-3) + ... + f(1) + f(0)]
         *        = 2 * f(n-2)
         * ------- 归纳 --------------------
         * f(n) = 2 * f(n-1)
**/

note_coding 文章被收录于专栏

记录自己的解题思路, 欢迎评价

全部评论

相关推荐

但我还是会继续秋招的
投递京东等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务