相关疑难解决方法(0)

所以,有人早些时候发布了这个问题,但基本上没有付出任何努力,它标记很差,然后关闭.尽管如此,我认为这可能是个好问题.我发帖是因为根据OP,我的回答(发表在评论中)与解决方案不一致.所以,我想弄清楚我做错了什么(假设他的答案确实正确):

我们有:

T(N) = T(N-1) + T(N-2) + T(N-3)

其中N> 3.他没有列出基本案例,但由于N> 3,我认为可能有3个基本案例T(3),T(2)和T(1).为了计算T(K),我们执行以下操作:

T(K) = T(K-1) + T(K-2) + T(K-3)

然后我们必须计算:

T(K-1) = T((K-1)-1) + T((K-1)-2) + T((K-1)-3)
T(K-2) = T((K-2)-1) + T((K-2)-2) + T((K-2)-3)
T(K-3) = T((K-3)-1) + T((K-3)-2) + T((K-3)-3)

等等......这是一个树形表示:

L0                                                  T(K)
                      /                              |                              \
L1               T(K-1)                            T(K-2)                           T(K-3)
          /         |     \                 /        |          \                 /   |     \
L2   T((K-1)-1) T((K-1)-2) T((K-1)-3)  T((K-2)-1) T((K-2)-2) T((K-2)-3) T((K-3)-1) T((K-3)-2) T((K-3)-3) …