LeetCode 3154 到达第K级台阶的方案数
方法1：数学
class Solution {
static int MX = 31;
static int[][] res = new int[31][31];
static { // 使用计算需要开 long
for (int i = 0; i < MX; i++) {
res[i][0] = res[i][i] = 1;
for(int j = 1; j < i; j++)
res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
}
}
public int waysToReachStair(int k) {
// n: 向上次数 idx: 所在最大位置 ans: 方案数
int n = 0, idx = 1, ans = 0;
while (idx - n - 1 <= k) { // idx - n - 1 是所在最小位置
if (idx - n - 1 <= k && k <= idx) // 从 n + 1 个位置中选 idx - k 个
ans += res[n + 1][idx - k];
n++; idx <<= 1;
}
return ans;
}
}