动态规化 (Dynamic Programming) 是个计算机领域里很重要的算法,我在高中参加过三次信息学奥林匹克竞赛 (ACM),每年必有一题用动归(DP)来解答. 动态规化其实就是 把问题分解成子问题+记忆子问题求解的一个过程.
你如何教你的孩子DP是什么呢?
比如:你给你的孩子5根火柴,你的孩子数了数然后说有5根.然后你再给你的孩子1根火柴然后问一共有多少根,这时候你的孩子会马上说出6根,因为他知道已经有5根了,再加上1根就是6根.
原理就是:把问题分析成更小的问题,并分而求之,子问题的解会被保存下来这样在求解更大的问题的时候就不需要再重新把中间结果再算一遍了.
动态规化的解法经常是较优的一种解法,我们来看这么一道面试题:
给定一个正整数,将它拆分成至少两个正整数,求出这些正整数的最大乘积.比如 整数2,可以拆分成1+1, 乘积是1,当输入是10,需要分解成3+3+4,这样所得的最大乘积是36.
你会怎么解?暴力搜索?这种解法不好写,而且时间复杂度也大.可以用回溯+剪枝,但时间复杂度也相对较大,特别是当N较大的时候也会时间太久Time Exceeded.
dynamic-programming-interview-questions
动规解答这题就较为简单.这题并没有让你详细写出怎么拆分的方案,只需要解出最大的乘积即可.所以我们有以下的方案:
f(n) = max(f(n), max(i – j, f(i – j)) * j)) for 1 <= j < i <= n
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public: int integerBreak(int n) { vector<int> f(n + 1, 0); f[1] = 0; f[2] = 1; for (int i = 2; i < n + 1; i ++) { for (int j = 1; j < i; j ++) { f[i] = max(f[i], max(i - j, f[i - j]) * j); } } return f[n]; } }; |
class Solution {
public:
int integerBreak(int n) {
vector<int> f(n + 1, 0);
f[1] = 0;
f[2] = 1;
for (int i = 2; i < n + 1; i ++) {
for (int j = 1; j < i; j ++) {
f[i] = max(f[i], max(i - j, f[i - j]) * j);
}
}
return f[n];
}
};我们用 f(n) 来表示整数N拆分后的最大乘积,那么我们当我们把整数 i 分解成两部分 i – j 和 j, 那么 最大乘积是 f(i – j) * j 和 (i – j) * j 的较大值.我们需要O(N^2)循环来寻求最优拆分法.
动规在计算 f(n) 的时候会需要取决于 f(i – j)的值,这时候每个f(m) 的值就会被保存起来以供之后迭代使用.这也是一个记忆的过程.以下实现就相对简单好理解.空间复杂度也是 O(N^2)
英文: Dynamic Programming – Integer Break
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK