class Solution {
public:
int waysToReachStair(int k) {
}
};
100298. 到达第 K 级台阶的方案数
给你有一个 非负 整数 k 。有一个无限长度的台阶，最低 一层编号为 0 。
虎老师有一个整数 jump ，一开始值为 0 。虎老师从台阶 1 开始，虎老师可以使用 任意 次操作，目标是到达第 k 级台阶。假设虎老师位于台阶 i ，一次 操作 中，虎老师可以：
i - 1 ，但该操作 不能 连续使用，如果在台阶第 0 级也不能使用。i + 2jump 处，然后 jump 变为 jump + 1 。请你返回虎老师到达台阶 k 处的总方案数。
注意 ，虎老师可能到达台阶 k 处后，通过一些操作重新回到台阶 k 处，这视为不同的方案。
示例 1：
输入：k = 0
输出：2
解释：
2 种到达台阶 0 的方案为：
示例 2：
输入：k = 1
输出：4
解释：
4 种到达台阶 1 的方案为：
提示：
0 <= k <= 109原站题解
rust 解法, 执行用时: 3 ms, 内存消耗: 2.1 MB, 提交时间: 2024-08-20 09:11:26
impl Solution {
pub 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 += Self::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: i64 = 1;
for i in (n - k + 1..=n).rev() {
ans *= i as i64;
ans /= (n - i + 1) as i64;
}
ans as i32
}
}
javascript 解法, 执行用时: 74 ms, 内存消耗: 49.6 MB, 提交时间: 2024-08-20 09:11:02
/**
* @param {number} k
* @return {number}
*/
var waysToReachStair = function(k) {
let n = 0, npow = 1, ans = 0;
while (true) {
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;
};
function comb(n, k) {
let ans = 1;
for (let i = n; i >= n - k + 1; --i) {
ans *= i;
ans /= n - i + 1;
}
return ans;
}
python3 解法, 执行用时: 122 ms, 内存消耗: 18.1 MB, 提交时间: 2024-05-19 23:41:53
class Solution:
def waysToReachStair(self, k: int) -> int:
@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int, pre_down: bool) -> int:
if i > k + 1:
return 0
res = 1 if i == k else 0
res += dfs(i + (1 << j), j + 1, False) # 操作二
if i and not pre_down:
res += dfs(i - 1, j, True) # 操作一
return res
return dfs(1, 0, False)
# 组合数学
def waysToReachStair2(self, k: int) -> int:
ans = 0
for j in range(30):
m = (1 << j) - k
if 0 <= m <= j + 1:
ans += comb(j + 1, m)
return ans
# 优化
def waysToReachStair3(self, k: int) -> int:
ans = 0
for j in count(max(k - 1, 0).bit_length()):
m = (1 << j) - k
if m > j + 1:
break
ans += comb(j + 1, m)
return ans
java 解法, 执行用时: 1 ms, 内存消耗: 39.6 MB, 提交时间: 2024-05-19 23:40:39
public class Solution {
private static final int MX = 31;
private static final int[][] c = new int[MX][MX];
static {
for (int i = 0; i < MX; 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];
}
}
}
public int waysToReachStair(int k) {
int ans = 0;
for (int j = 0; j < 30; j++) {
int m = (1 << j) - k;
if (0 <= m && m <= j + 1) {
ans += c[j + 1][m];
}
}
return ans;
}
}
java 解法, 执行用时: 47 ms, 内存消耗: 43.7 MB, 提交时间: 2024-05-19 23:40:26
class Solution {
public int waysToReachStair(int k) {
return dfs(1, 0, 0, k, new HashMap<>());
}
private int dfs(int i, int j, int preDown, int k, Map<Long, Integer> memo) {
if (i > k + 1) {
return 0;
}
long p = ((long) i << 32) | j << 1 | preDown; // 用一个 long 表示状态
if (memo.containsKey(p)) { // 之前算过了
return memo.get(p);
}
int res = i == k ? 1 : 0;
res += dfs(i + (1 << j), j + 1, 0, k, memo); // 操作二
if (preDown == 0 && i > 0) {
res += dfs(i - 1, j, 1, k, memo); // 操作一
}
memo.put(p, res); // 记忆化
return res;
}
}
cpp 解法, 执行用时: 73 ms, 内存消耗: 32.5 MB, 提交时间: 2024-05-19 23:40:15
class Solution {
unordered_map<long long, int> memo;
int dfs(int i, int j, bool preDown, int k) {
if (i > k + 1) {
return 0;
}
long long p = (long long) i << 32 | j << 1 | preDown; // 用一个 long long 表示状态
if (memo.contains(p)) { // 之前算过了
return memo[p];
}
int res = i == k;
res += dfs(i + (1 << j), j + 1, false, k); // 操作二
if (i && !preDown) {
res += dfs(i - 1, j, true, k); // 操作一
}
return memo[p] = res; // 记忆化
};
public:
int waysToReachStair(int k) {
return dfs(1, 0, false, k);
}
};
cpp 解法, 执行用时: 0 ms, 内存消耗: 7.1 MB, 提交时间: 2024-05-19 23:40:03
int c[31][31];
auto init = [] {
for (int i = 0; i < 31; 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];
}
}
return 0;
}();
class Solution {
public:
int waysToReachStair(int k) {
int ans = 0;
for (int j = k > 1 ? 32 - __builtin_clz(k - 1) : 0; (1 << j) - k <= j + 1; j++) {
ans += c[j + 1][(1 << j) - k];
}
return ans;
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2024-05-19 23:39:50
// 组合数学
const mx = 31
var c [mx][mx]int
func init() {
for i := 0; i < mx; i++ {
c[i][0], c[i][i] = 1, 1
for j := 1; j < i; j++ {
c[i][j] = c[i-1][j-1] + c[i-1][j]
}
}
}
func waysToReachStair(k int) (ans int) {
for j := bits.Len(uint(max(k-1, 0))); 1<<j-k <= j+1; j++ {
ans += c[j+1][1<<j-k]
}
return
}
golang 解法, 执行用时: 41 ms, 内存消耗: 6.9 MB, 提交时间: 2024-05-19 23:39:24
// 记忆化搜索
func waysToReachStair(k int) int {
type args struct {
i, j int
preDown bool
}
memo := map[args]int{}
var dfs func(int, int, bool) int
dfs = func(i, j int, preDown bool) int {
if i > k+1 {
return 0
}
p := args{i, j, preDown}
if v, ok := memo[p]; ok { // 之前算过了
return v
}
res := dfs(i+1<<j, j+1, false) // 操作二
if !preDown && i > 0 {
res += dfs(i-1, j, true) // 操作一
}
if i == k {
res++
}
memo[p] = res // 记忆化
return res
}
return dfs(1, 0, false)
}