作者ledia (下班後才下棋)
看板C_and_CPP
标题Re: [问题] 动态规划的问题
时间Sat Aug 8 01:25:56 2009
※ 引述《henry035 (Rex)》之铭言：
: 简化过的题目：
: 求整数 1 ~ N 组成和为 S 的方式有几种？ (1 ~ N 各只能取一次)
: EX： N = 4 , S = 5 总共有两种组成方式， 1 + 4 、 2 + 3
: 我用递回的方式列举虽然可解，但太慢(超时)，请想问怎麽用动态规划的演算法解？
: 有找到动态规划的式子，如下：
: A[i][j] = A[i-1][j] + A[i-1][j-i] j-i>=0
: A[i][j] = A[i-1][j] j-i< 0
: A[i][j] 代表 1 ~ i 使和为 j 的方法数
: 但实在不是很懂，想请问这是怎麽想出来的，而且为什麽是这样？
先假设 S >= N
S 用 1 ~ N 的所有组法可分成两种 case:
(a) 有用到 N 的
(b) 没有用到 N 的
(a) 用到 N 的那部份
等於是 S-N 用 1 ~ (N-1) 组出来的每个解
再附加 N 到最後面
所以算次数就等价於去求用 1 ~ (N-1) 去组出 S-N
(b) 没有用到 N 的那部份的次数
其实就等於是 S 用 1 ~ (N-1) 组出来的每个解
容易证明 (a) 和 (b) 是不会互相重覆的, 而且包含全部可能
(上一句是废话, 一个有 N, 一个没有 N 嘛 XD)
由集合的加法原则
我们可以推论出
A[i][j] = A[i-1][j] + A[i-1][j-i]
当然在 S < N 的时候
(a) 是不存在的, 所以只有 (b) 的 case, 式子变成
A[i][j] = A[i-1][j]
这样的说明有比较清楚吗 ? ^^|
--
有时候，遗忘，是令人快乐的。什麽时候？当然是有人伤了你的心的时候。
存心伤你的那个人，固然是故意和你过不去，但是被伤了心而耿耿於怀的你
，却是和自己过不去了。所以，记性不好的人，通常会是比较快乐的人，也
是比较不容易被击倒的人。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.49
※ 编辑: ledia 来自: 140.112.30.49 (08/08 01:27)
1F：推 henry035:概念了解了，也比较能体会怎麽从 Divide and Conquer 08/08 04:16
2F：→ henry035:推演出这个想法，谢谢大大您费时解说。 08/08 04:16
3F：→ henry035:但想追问一个问题，底层的数值要怎麽设呢？ 08/08 04:17
4F：→ henry035:A[2][3] = A[1][3] + [1][2] 但是 08/08 04:18
5F：→ henry035:A[2][3] = 1, [1][3] = 0, A[1][2] = 0 08/08 04:18
6F：→ ledia:A[2][3] = A[1][3] + A[1][1] ...... 我忘了提到了 08/08 10:59
7F：→ ledia:初始值的话 1+...+i == j -> 1, 1+...+i < j -> 0 08/08 11:01
8F：→ ledia:如果觉得某等式有问题, 就去直接拆解思考等号两边的真实意义 08/08 11:02
9F：→ ledia:有例外就会找到例外, 式子代错也可以因此发现 08/08 11:02
10F：推 henry035:谢谢大大您指出我的脑残错误~ 感谢 08/08 11:28
11F：→ ledia:这不脑残呀... 我一开始看到也在想是不是有什麽没想到 XD 08/08 12:28