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;}
};