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[1]
题目来自leetcode3154。
大体步骤如下：1.使用动态规划来解决问题，定义一个函数 waysToReachStair 来计算到达第k级台阶的方案数。
2.在该函数中，根据 Alice 的移动规则，采用迭代的方式计算到达每一级台阶的方案数。
3.使用组合数的方式，计算不同移动方式的组合数，更新方案数。
4.返回到达第k级台阶的所有可能方案的数量。
时间复杂度分析：
• 由于需要进行迭代计算每一级台阶的方案数，时间复杂度为 O(log k)。空间复杂度分析：
• 算法使用了常数级别的额外空间，主要用于变量和存储计算结果，因此空间复杂度为 O(1)。Go完整代码如下：package mainimport ( "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));}
引用链接[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP
