使用迭代方法求解杆切割问题（无 DP）的递推关系
Solving the recurrence relation for rod cutting problem (without DP) using iteration method
我正在阅读 CLRS 书中的动态规划章节。在切杆问题中，当我们不使用动态规划（基本情况 T(0) = 1）时，会得到 this recurrence relation。解直接给出为 T(n) = 2^n.
我可以使用归纳验证解决方案是否正确。但我似乎无法弄清楚如何使用迭代（即插即用）方法从给定的重复中逐步得出这个解决方案。如果能在这件事上提供帮助，我将不胜感激。
T(0) = 1
T(1) = 1 + T(0)
= 2
T(2) = 1 + T(0) + T(1)
\_,____/
= T(1) + T(1)
= 2*T(1)
= 4
T(3) = 1 + T(0) + T(1) + T(2)
\_,___________/
= T(2) + T(2)
= 2*T(2)
= 8
T(4) = 1 + T(0) + T(1) + T(2) + T(3)
\_,__________________/
= T(3) + T(3)
= 2*T(3)
= 16
:
T(n) = 2*T(n-1) = 2^n
我正在阅读 CLRS 书中的动态规划章节。在切杆问题中，当我们不使用动态规划（基本情况 T(0) = 1）时，会得到 this recurrence relation。解直接给出为 T(n) = 2^n.
我可以使用归纳验证解决方案是否正确。但我似乎无法弄清楚如何使用迭代（即插即用）方法从给定的重复中逐步得出这个解决方案。如果能在这件事上提供帮助，我将不胜感激。
T(0) = 1
T(1) = 1 + T(0)
= 2
T(2) = 1 + T(0) + T(1)
\_,____/
= T(1) + T(1)
= 2*T(1)
= 4
T(3) = 1 + T(0) + T(1) + T(2)
\_,___________/
= T(2) + T(2)
= 2*T(2)
= 8
T(4) = 1 + T(0) + T(1) + T(2) + T(3)
\_,__________________/
= T(3) + T(3)
= 2*T(3)
= 16
:
T(n) = 2*T(n-1) = 2^n