首页 > 代码库 > [DP] Rod-cutting problem
[DP] Rod-cutting problem
给一个长度为 n 的杆子,切成小段卖出去,价格根据小段的长度不同而不同。下面是一个例子
我们要通过切成小段卖出尽可能高的总价钱。问题是:How to decompose the problem?
Decomposition 的第一步是:第一刀切在哪?可以切在最左边(等于整根卖出去);可以切在位置1,位置2,。。。
关键的一点是,刀切下去后,左半段就不再切了,继续切右半段。切右半段就变成了一个subproblem。
Naive Recursion:
Top-down implementation:
Bottom-up implementation: 不容易构想,变量 j 是 subproblem‘s size,从1递增到n,变量 i 用来把每个subproblem 拆分成更小的subproblem,而根据我们这种计算的顺序,当计算 size = j 的时候,< j 的 subproblem 已经计算完毕了。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。