题解 | #跳台阶扩展问题#
跳台阶扩展问题
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]; } };
这里还是得做归纳:
- 第 n 阶 的台阶数量等于 前n-1 阶方法的总和 + 1 --》 f(n) = f(n-1) + f(n-2) + ... f(2) + f(1) + 1
- 将 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 文章被收录于专栏
记录自己的解题思路, 欢迎评价