3154. 到达第 K 级台阶的方案数（24.8.20）

今天发晚了，嘿嘿，玩黑神话玩的

题目

给你有一个 非负 整数 k 。有一个无限长度的台阶，最低 一层编号为 0 。

Alice 有一个整数 jump ，一开始值为 0 。Alice 从台阶 1 开始，可以使用 任意 次操作，目标是到达第 k 级台阶。假设 Alice 位于台阶 i ，一次 操作 中，Alice 可以：

向下走一级到 i - 1 ，但该操作 不能 连续使用，如果在台阶第 0 级也不能使用。
向上走到台阶 i + 2jump 处，然后 jump 变为 jump + 1 。
请你返回 Alice 到达台阶 k 处的总方案数。

注意，Alice 可能到达台阶 k 处后，通过一些操作重新回到台阶 k 处，这视为不同的方案。

示例 1：

输入：k = 0
输出：2
解释：
2 种到达台阶 0 的方案为：

• Alice 从台阶 1 开始。
  - 执行第一种操作，从台阶 1 向下走到台阶 0 。
• Alice 从台阶 1 开始。
  • 执行第一种操作，从台阶 1 向下走到台阶 0 。
  • 执行第二种操作，向上走 20 级台阶到台阶 1 。
  • 执行第一种操作，从台阶 1 向下走到台阶 0 。

示例 2：
输入：k = 1
输出：4
解释：
4 种到达台阶 1 的方案为：

• Alice 从台阶 1 开始，已经到达台阶 1 。

• Alice 从台阶 1 开始。

  • 执行第一种操作，从台阶 1 向下走到台阶 0 。
  • 执行第二种操作，向上走 20 级台阶到台阶 1 。

• Alice 从台阶 1 开始。

  • 执行第二种操作，向上走 20 级台阶到台阶 2 。
  • 执行第一种操作，向下走 1 级台阶到台阶 1 。

• Alice 从台阶 1 开始。

  • 执行第一种操作，从台阶 1 向下走到台阶 0 。
  • 执行第二种操作，向上走 20 级台阶到台阶 1 。
  • 执行第一种操作，向下走 1 级台阶到台阶 0 。
  • 执行第二种操作，向上走 21 级台阶到台阶 2 。
  • 执行第一种操作，向下走 1 级台阶到台阶 1 。

提示：

0 <= k <= 109

解题思路

到达 i 的台阶可以的方式是：1. 本身就在 i 处  --   1种2. 通过 上升 得到   3. 通过 下降 得到4. 先上升 后下降5. 先下降 后上升
其实可以简化为：1. 本身就在 i 处  --   1种2. 先上升了(先假设为 a ) 2^0+2^1+2^2+...+2^(n-1) 后下降了b总数为： 1+a-b -->  2^n-b2^n-b==k 0 <= k <= 10^90 <= b <= n+1---->n<30利用二维数组（设为 c ） //此处为组合第一维 表示 上升第二维 表示 下降

代码

class Solution {
public:int waysToReachStair(int k) {const int MAXS=31;int c[MAXS][MAXS]={};for(int i=0;i<MAXS;i++){c[i][0]=c[i][i]=1;for(int j=1;j<i;j++){c[i][j]=c[i-1][j-1]+c[i-1][j];}}int ans=0;for(int n=0;n<MAXS-1;n++){int b=(1<<n)-k;if(b>=0&&b<=n+1){ans+=c[n+1][b];}}return ans;}
};