algorithm - 用迭代法求解杆切割问题的递推关系(无DP)
问题描述
我正在阅读 CLRS 书中的动态编程章节。在棒材切割问题中,这种递推关系是在我们不使用动态规划(基本情况 T(0) = 1)时得到的。解直接给出为 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
推荐阅读
- c - 在用户输入的 ID 号前加上“0”
- javascript - 如何告诉父类元素在 ReactJS 中发生了变化?
- mysql - 如何仅在包含更改时才使用触发器在历史表中添加数据
- elixir - Ecto/Phoenix 上的多态性与在 Rails 上创建的数据库
- google-bigquery - 用于射击图的 Bigquery GIS
- javascript - 按出现的元素频率对数组进行排序
- neo4j - 有没有办法可以根据不同的条件从 neo4j 数据库中获取数据
- powershell - 从 Get-ADUser 和 Get-ADComputer 获取属性列表
- c# - C# 中的 LINQ 查询?
- ios - 如何将 UIView 插入 MSMessage?