给一个长度为 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 已经计算完毕了。
[DP] Rod-cutting problem的更多相关文章
-
动态规划法(五)钢条切割问题(rod cutting problem)
继续讲故事~~ 我们的主人公现在已经告别了生于斯,长于斯的故乡,来到了全国最大的城市S市.这座S市,位于国家的东南部,是全国的经济中心,工商业极为发达,是这个国家的人民所向往的城市.这个到处都 ...
-
poj3311 TSP经典状压dp(Traveling Saleman Problem)
题目链接:http://poj.org/problem?id=3311 题意:一个人到一些地方送披萨,要求找到一条路径能够遍历每一个城市后返回出发点,并且路径距离最短.最后输出最短距离即可.注意:每一 ...
-
递推DP HDOJ 5328 Problem Killer
题目传送门 /* 递推DP: 如果a, b, c是等差数列,且b, c, d是等差数列,那么a, b, c, d是等差数列,等比数列同理 判断ai-2, ai-1, ai是否是等差(比)数列,能在O( ...
-
rod cutting
for a rod of length i the price of it si pi,to cut the rod to earn more money package dynamic_progra ...
-
[Java 8] (9) Lambda表达式对递归的优化(下) - 使用备忘录模式(Memoization Pattern) .
使用备忘录模式(Memoization Pattern)提高性能 这个模式说白了,就是将需要进行大量计算的结果缓存起来,然后在下次需要的时候直接取得就好了.因此,底层只需要使用一个Map就够了. 但是 ...
-
【HDU 5909】 Tree Cutting (树形依赖型DP+点分治)
Tree Cutting Problem Description Byteasar has a tree T with n vertices conveniently labeled with 1,2 ...
-
10003 Cutting Sticks(区间dp)
Cutting Sticks You have to cut a wood stick into pieces. The most affordable company, The Analog ...
-
UVA 10003 Cutting Sticks(区间dp)
Description Cutting Sticks You have to cut a wood stick into pieces. The most affordable company ...
-
BZOJ1003 物流运输 最短路+DP
1003: [ZJOI2006]物流运输 Description 物流公司要把一批货物从码头A运到码头B.由于货物量比较大,需要n天才能运完.货物运输过程中一般要转停好几个码头.物流公司通常会设计一条 ...
-
动态规划——线性dp
我们在解决一些线性区间上的最优化问题的时候,往往也能够利用到动态规划的思想,这种问题可以叫做线性dp.在这篇文章中,我们将讨论有关线性dp的一些问题. 在有关线性dp问题中,有着几个比较经典而基础的模 ...
随机推荐
- ios枚举规范
-
【转载】James Whittaker:经营成功的测试职业生涯
转注:这篇文章出自 James A. Whittaker ,但未找到原始出处/译者.如果有知道原始出处的朋友,可在评论这留言. 你是如何开始做测试工作的? 1989年,我在田纳西大学读研究生的时候, ...
-
UOJ Test Round 1
第一题: 题目大意: 给出N个字符串,字符串的前面部分都是字母且都是一样的,后面部分是数字,按照后面的数字排序.N<=10000 解题过程: 1.第一题是真良心,一开始的做法是把后面的数字分离出 ...
-
二、JavaScript语言--JS基础--JavaScript进阶篇--数组
1.什么事数组 我们知道变量用来存储数据,一个变量只能存储一个内容.假设你想存储10个人的姓名或者存储20个人的数学成绩,就需要10个或20个变量来存储,如果需要存储更多数据,那就会变的更麻烦.我们用 ...
-
IOS Crash捕获
IOS Crash ,就两种情况:一种是异常,另一种是中断[信号量]. #include <libkern/OSAtomic.h> #include <execinfo.h> ...
-
C#逻辑运算符详解
代码如下: namespace ConsoleApplication1 { class @class { static void Main_1(string[] args) //输出用户输入的内容 { ...
-
mvc @html.editor怎么修改宽度 和其他属性
<style type="text/css"> #dob { width:6em; } </style> @using (Html.BeginForm()) ...
-
[自制操作系统] 图形界面&VBE工具&MMIO显存&图形库/字库
本文记录了在JOS(或在任意OS)上实现图形界面的方法与一些图形库的实现. 本文中支持的新特性: 支持基本图形显示 支持中英文显示(中英文点阵字库) 相关:VBE VESA MMIO 点阵字库 Git ...
-
Oracle课程档案,第一天。
sys是Oracle最高权限者 DBSNMP:简单网络管理系统 ctrl+d回到oracle目录 在SQL中输入 exit也可以 select:列 where:行 sqlplus / as sysdb ...
-
hadoop关联文件处理
c001.txt ------------------------------ filetype|commid|commname|addressidcomm|1|罗湖小区1|1comm|2|罗湖小区2 ...