2024-12-27：到达第 K 级台阶的方案数。用go语言，给定一个非负整数 k，我们有一个无限长度的台阶，从第 0 层开始编号。
Alice 从第 1 层出发，并拥有一个初始值为 0 的变量 jump。

她可以通过以下两种操作在台阶之间移动：

1.向下移动到第 i - 1 层，但这个操作不能连续使用，且在第 0 层时无法再向下移动。

2.向上移动到第 i + 2^jump 层，同时将 jump 的值增加 1。

Alice 的目标是到达第 k 层。请你计算她到达第 k 层的所有可能方案的数量。

需要注意的是，如果 Alice 在到达第 k 层后通过某些操作再次返回到 k 层，这也被视为一种不同的方案。

0 <= k <= 1000000000。

输入：k = 0。

输出：2。

解释：

2 种到达台阶 0 的方案为：

1.Alice 从台阶 1 开始。

1.1.执行第一种操作，从台阶 1 向下走到台阶 0 。

2.Alice 从台阶 1 开始。

2.1.执行第一种操作，从台阶 1 向下走到台阶 0 。

2.2.执行第二种操作，向上走 20 级台阶到台阶 1 。

2.3.执行第一种操作，从台阶 1 向下走到台阶 0 。

答案2024-12-27：

chatgpt

题目来自leetcode3154。

大体步骤如下：

1.使用动态规划来解决问题，定义一个函数 waysToReachStair 来计算到达第k级台阶的方案数。

2.在该函数中，根据 Alice 的移动规则，采用迭代的方式计算到达每一级台阶的方案数。

3.使用组合数的方式，计算不同移动方式的组合数，更新方案数。

4.返回到达第k级台阶的所有可能方案的数量。

时间复杂度分析：

• 由于需要进行迭代计算每一级台阶的方案数，时间复杂度为 O(log k)。

空间复杂度分析：

• 算法使用了常数级别的额外空间，主要用于变量和存储计算结果，因此空间复杂度为 O(1)。

Go完整代码如下：

package main

import (
	"fmt"
)

func waysToReachStair(k int) int {
	n, npow, ans := 0, 1, 0
	for {
		if npow-n-1 <= k && k <= npow {
			ans += comb(n+1, npow-k)
		} else if npow-n-1 > k {
			break
		}
		n++
		npow *= 2
	}
	return ans
}

func comb(n, k int) int {
	ans := 1
	for i := n; i >= n-k+1; i-- {
		ans *= i
		ans /= n - i + 1
	}
	return ans
}

func main() {
	k := 0
	fmt.Println(waysToReachStair(k))
}

Rust完整代码如下：

fn ways_to_reach_stair(k: i32) -> i32 {
    let mut n = 0;
    let mut npow = 1;
    let mut ans = 0;
    
    loop {
        if npow - n - 1 <= k && k <= npow {
            ans += comb(n + 1, npow - k);
        } else if npow - n - 1 > k {
            break;
        }
        n += 1;
        npow *= 2;
    }

    ans
}

fn comb(n: i32, k: i32) -> i32 {
    let mut ans = 1;
    
    for i in n..=n-k+1 {
        ans *= i;
        ans /= n - i + 1;
    }

    ans
}

fn main() {
    let k = 0;
    println!("{}", ways_to_reach_stair(k));
}