[dp_math]变态跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路：

dp思路:
按照上题的思路直接到dp一步：dp(n)=dp(n-1)+dp(n-2)+...+dp(1)+dp(0)
              dp(1)=1,dp(0)=1;
至此dp结束~, 接着是研究一下会发现因为头两项的缘故导致：dp(n)=2*dp(n-1)

规律性这么强，对此排列组合的思路：

• 1.还是如上题从最大的一项入手分情况（整数划分的思路），是个台阶为例，最大一项是3的情况，则剩下7继续以最大为3划分，是个子问题，而这种解法启图知道多少个3多少个2多少个1来排列，现在要知道每个划分段的个数涉及递归和dp就省不了空间，或者是直接递归模拟，不用先分堆法在排列（省去排列计算）则是搜索型，所以这种思路没前途还复杂（需要视具体每种方案计算），而且排列组合就是为了不递归自己可算，这里违背了初衷。
• 2.从具体划分情况入手，举几个例子10的情况可以是3331，3322，33111，这里的关键是凑成10，然后这几个例子的区别是用几个小的替换大的，即吧10切割的更碎，所以解决的思路是吧问题视为如果把10切碎（各种切法），于是回归到切绳子和整数划分（分先后序且无规定段数/个数版），数学上的隔板问题：C(0, n-1)+C(1, n-1)+...C(n-1, n-1)=2^n-1。
• 3.结合2，还可以另一种解释即每一个台阶都要考虑选不选的解构方法，所以3331的情况就是0010010011（最后一阶肯定选所以二叉分枝最后一支少了不选的情况，叶子节点数2^n-1）。

然后是实现2^n可以用位移运算

#include <iostream>
#include <vector>
using  namespace std;
class Solution {
public:

    int jumpFloorII(int number) {
        return 1<<(number-1);
    }
};