建个人网站做导购,免费网站创建,流行网站开发框架,网站模板设计报价单今天发晚了#xff0c;嘿嘿#xff0c;玩黑神话玩的 题目 给你有一个 非负 整数 k 。有一个无限长度的台阶#xff0c;最低 一层编号为 0 。 Alice 有一个整数 jump #xff0c;一开始值为 0 。Alice 从台阶 1 开始#xff0c;可以使用 任意 次操作#xff0c;目标是到达… 今天发晚了嘿嘿玩黑神话玩的 题目 给你有一个 非负 整数 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^02^12^2...2^(n-1) 后下降了b总数为 1a-b -- 2^n-b2^n-bk 0 k 10^90 b n1----n30利用二维数组设为 c //此处为组合第一维 表示 上升第二维 表示 下降代码
class Solution {
public:int waysToReachStair(int k) {const int MAXS31;int c[MAXS][MAXS]{};for(int i0;iMAXS;i){c[i][0]c[i][i]1;for(int j1;ji;j){c[i][j]c[i-1][j-1]c[i-1][j];}}int ans0;for(int n0;nMAXS-1;n){int b(1n)-k;if(b0bn1){ansc[n1][b];}}return ans;}
};
