软件工程师面试技巧之: 动态规划/整数拆分

动态规化 (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

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

PS: 据说现在互联网大厂已经不爱面动态规划的题了, 一是因为有点难, 二是感觉工作中用不上.

面试经历

面试题

面试技巧

面试其它

GD Star Rating
loading...

本文一共 589 个汉字, 你数一下对不对.

软件工程师面试技巧之: 动态规划/整数拆分. (AMP 移动加速版本)
上一篇: 软件工程师面试技巧之如何检查数独的有效性
下一篇: 从A到B再到C有多少种方法?

赞赏我的几个理由.

¥ 打赏支持

扫描二维码，分享本文到微信朋友圈

小赖子的英国生活和资讯

软件工程师面试技巧之: 动态规划/整数拆分

面试经历

面试题

面试技巧

面试其它

评论

面试经历

面试题

面试技巧

面试其它

相关文章：

评论