pypy3 解法, 执行用时: 87ms, 内存消耗: 48836K, 提交时间: 2022-09-07 22:21:46

import math
n, d = map(int, input().split())
f = [0] * 1005
f[1] = 1
for i in range(2, n - d):
    f[i] = f[i - 1] + 1
    if i >= d + 1:
        f[i] += f[i - d - 1]
print(int((1 << n - 1) - 1 - f[n - d - 1]))

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 472K, 提交时间: 2018-10-02 15:58:24

#include<cstdio>
long long n,d,dp[130];
int main(){
	scanf("%lld%lld",&n,&d);
	for(int i=n-d-1;i>=1;i--)dp[i]=dp[i+1]+dp[i+d+1]+1;
	printf("%lld\n",(1ll<<(n-1))-1-dp[1]);
	return 0;
}

Python3 解法, 执行用时: 44ms, 内存消耗: 4516K, 提交时间: 2022-11-16 00:37:50

n, d = map(int,input().split())
f=[0 for i in range(140)]
f[1]=1
for i in range(2, n+1):
    f[i] = 1 + f[i - 1] + f[i - d - 1]
print((1 << n - 1) - 1 - f[n - d - 1])