使用步骤1、2和3计算到达第n个步骤的方式，但只执行步骤3 k次

Question

我可以使用递归来解决这个问题。这是代码

int countstep(int n,int k){
if(n<0)
return 0;
if(n==0)
return 1;
int total_step=countstep(n-1,k)+countstep(n-2,k);
if(k>0)
total_step+=countstep(n-3,k-1);
return total_step;
}

问题是，我不知道如何以制表的方式实现这一点。

Answer 1

代码本质上与递归公式相同，只是为n和k的每个可能值计算函数(不超过限制(，并将结果存储在大小适当的数组(表(中。您必须小心，不要越界访问该表。

以下是Python中的一个解决方案，它针对可读性而不是最大效率进行了优化。

def countstep(N, K):
table = [[None] * (K+1) for _ in range(N+1)]
for k in range(K+1):
table[0][k] = 1
for n in range(1, N+1):
for k in range(K+1):
t = 0
if n >= 1:
t += table[n-1][k]
if n >= 2:
t += table[n-2][k]
if n >= 3 and k > 0:
t += table[n-3][k-1]
table[n][k] = t
return table[N][K]

您可以小心地按K+1使表为4，而不是按N+1使表为K+1，因为在每一点上，您只对N的最后4个值的表条目感兴趣。这里有一个版本可以做到这一点(请注意，它使用python功能，访问具有负索引的数组会从列表末尾返回一个元素(例如：table[-2]是table的倒数第二行((。

def countstep(N, K):
table = [[None] * (K+1) for _ in range(4)]
for k in range(K+1):
table[0][k] = 1
for n in range(1, N+1):
for k in range(K+1):
ti = n % 4
t = 0
if n >= 1:
t += table[ti-1][k]
if n >= 2:
t += table[ti-2][k]
if n >= 3 and k > 0:
t += table[ti-3][k-1]
table[ti][k] = t
return table[N%4][K]