主题：[讨论]请问各位什么叫动态规划?
编程黑客
[专家分：1660] 发布于 2006-11-04 11:22:00
问题如题
老师没讲过,马上又要竞赛
只能在这里问问拉
回复列表 （共10个回复）
沙发
bigchen [专家分：1940] 发布于 2006-11-04 12:03:00
所谓动态规划是一种算法，可以解决很多问题
但是用动态规划解决的问题有三个特点，缺一不可：
1、具有最优子结构
2、无后效性
3、子问题的重叠性
动态规划的主要思想是：自顶向下分析，自底向上计算
最重要的就是找到动态规划方程来解决问题。
动态规划虽然思想好理解，但是解问题还是很具有挑战性的。
板凳
Benix [专家分：720] 发布于 2006-11-05 00:12:00
自己找本书看看 别老等老师讲
我们老师就从不讲课 从小学毕业就是我自学
动规要说的东西很多 不是一两句就行的
所以还是自己看书把
3 楼
编程黑客 [专家分：1660] 发布于 2006-11-05 10:46:00
动态规划是不是几乎每年都会考啊？？
4 楼
bigchen [专家分：1940] 发布于 2006-11-05 15:58:00
不是拉
没有那么恐怖
5 楼
Benix [专家分：720] 发布于 2006-11-05 16:44:00
4楼为什么这样说 明确地讲 就近几年的势头来看 动规必考
6 楼
编程黑客 [专家分：1660] 发布于 2006-11-05 21:13:00
怕啊!!!
那就说明我一定有一题是0分了啦~
7 楼
bigchen [专家分：1940] 发布于 2006-11-05 21:49:00
一道题0分很正常,不用怕.其他分抓住就可以了,难道江苏每年人人都是4题全部都有分?
8 楼
Benix [专家分：720] 发布于 2006-11-05 23:06:00
动规其实不太难 如果你有递归和递推的基础就可以比较快的理解
如果片面一点说 动规可以理解为递推
9 楼
Benix [专家分：720] 发布于 2006-11-05 23:08:00
给你到动规的题练练吧
118号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高，技术不是十分完善，所以工厂生产的锎成品可能会有3种不同的纯度，A：100%，B：1%，C：0.01%，为了出售方便，必须把不同纯度的成品分开装箱，装箱员grant第1次顺序从流水线上取10个成品（如果一共不足10个，则全部取出），以后每一次把手中某种纯度的成品放进相应的箱子，然后再从流水线上顺序取一些成品，使手中保持10个成品（如果把剩下的全部取出不足10个，则全部取出），如果所有的成品都装进了箱子，那么grant的任务就完成了。
由于装箱是件非常累的事情，grant希望他能够以最少的装箱次数来完成他的任务，现在他请你编个程序帮助他。
输入
第1行为n（1<=n<=100），为成品的数量
以后n行，每行为一个大写字母A，B或C，表示成品的纯度。
输出
仅一行，为grant需要的最少的装箱次数。
输入样例
11
A
B
C
A
B
C
A
B
C
A
B
输出样例
3
10 楼
编程黑客 [专家分：1660] 发布于 2006-11-06 22:21:00
能把题目解释得通俗一点吗
我来回复
您所在位置：社区首页 — PASCAL语言讨论区 — [讨论]请问各位什么叫动态规划?