计算从起始石头到达终点并返回的方法，无需使用同一块石头两次，每一步最多跳跃 K 次

Question

理查德是一只定期往返于加拿大和美国之间的企鹅。

具体来说，加拿大位于位置 1 ，美国位于位置 N。 在位置 2 到 N 中，有理查德可以跳上的冰块。 Richard 可以从位置 i 跳到位置 j 当且仅当 abs(i-j)<=k.

理查德不相信浪费时间，所以当他朝一个方向通勤时，他总是会朝那个方向移动。这意味着从加拿大通勤到美国时，地点数量单调增加，而从美国通勤到加拿大时，地点数量单调减少。

在加拿大和美国之间的冰雪融化的秋季和春季期间，理查德的通勤变得很复杂。如果理查德跳到冰块上，该冰块将融化到足以在回程中无法使用的程度。

计算理查德可以从加拿大到美国往返的不同方式的数量。如果理查德在某个方向上使用冰块以一种方式沿该方向移动，但不以另一种方式移动，则两种方式是不同的。

2<=k<=N<=5000

输入示例： 5 3 样本输出 12

我应该如何解决这个问题？

n = 5000
k = 400
dp = [[0]*(n+1) for _ in range(n+1)]
dp[1][1] = 1

start_time = time.time()

for i in range(2, n+1):
    total = 0
    for j in range(i-k, i):
        dp[j][i] = dp[j][j]
        total += dp[j][i]
    dp[i][i] = total

end_time = time.time()


print(dp[-1][-1] % 998244353)

这是我计算去那里的代码，但是返回的路呢？

your text

Answer 1

想象一下给岩石 2 到 N-1 着色。如果在从加拿大到美国的途中使用，则将其涂成红色；如果在返回途中使用，则将其涂成蓝色。如果根本不使用它们，请将它们保留为灰色。你的问题是有多少种方法可以给岩石着色，使得不存在 >= k 个非红色石头或非蓝色石头的间隙。

制作一个矩阵 DP[r][b]，其中包含给棋子着色的方法数量，使得最高的红色棋子为 r，最高的蓝色棋子为 b，并且不存在非法的红色间隙 < r or blue gaps < b.

如果按照 r+b、max(r,b) 等递增的顺序填充矩阵，则可以在 O(k) 时间内从先前填充的元素计算出每个元素。然后，给定填充的矩阵，您的最终答案可以在 O(k²) 时间内计算出来。

由于矩阵的大小为 (N-2)²，因此这需要 O(kN²) 时间。