美文网首页动态规划剑指Offer
4.3 动态规划 DP(2)

4.3 动态规划 DP(2)

作者: coderjiege | 来源:发表于2017-12-30 21:29 被阅读61次

    套路

    • 关键字:第N个,最大和
    • 后面的值由前面的值依次推导而来,为了充分利用上一次的结果,于是出现了最优解:动态规划。
    • 如何知道这是一道动态规划题目?一般涉及到最优解,比如说最大值等最值问题。特点:中途遍历过的结果可能对后续遍历结果有帮助,而不需要再重新做计算,如果能够充分利用这些结果,那么就是动态规划的解法。这种解法往往最优,所以是DP是算法的最优解的一种。

    注意点

    • 暂无

    目录

    • 丑数
    • 连续子数组的最大和

    丑数

    把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

    • 后面的丑数由前面的丑数乘以2,3,5中的一个得来。因此可以用动态规划(DP)去解
    public int GetUglyNumber_Solution(int index) {
        if (index <= 0) return 0;
        int[] uglyNumbers = new int[index];
        uglyNumbers[0] = 1;
        int i2 = 0, i3 = 0, i5 = 0;
        for (int i = 1; i < index; i++) {
            int m2 = uglyNumbers[i2] * 2;
            int m3 = uglyNumbers[i3] * 3;
            int m5 = uglyNumbers[i5] * 5;
            // 只用比较三个数:
            // 用于乘2的最小丑数(m2),用于乘3的最小丑数(m3),用于乘5的最小丑数(m5)
            int uglyNumber = min(min(m2, m3), m5);
            uglyNumbers[i] = uglyNumber;
            if (uglyNumbers[i] == m2) i2++;
            if (uglyNumbers[i] == m3) i3++;
            if (uglyNumbers[i] == m5) i5++;
        }
        return uglyNumbers[index - 1];
    }
    

    连续子数组的最大和

    HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住?(子向量的长度至少是1)

    • maxSum 保存连续子向量最大和
    • curSum 保存包含当前遍历元素的可能对maxSum有贡献(和大于0)的连续子序列,留着"将来"可能用得上-.-
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int curSum = array[0], maxSum = array[0];
        for (int i = 1; i < array.length; i++) {
            curSum = curSum > 0 ? curSum + array[i] : array[i];
            maxSum = curSum > maxSum ? curSum : maxSum;
        }
        return maxSum;
    }
    

    相关文章

      网友评论

        本文标题:4.3 动态规划 DP(2)

        本文链接:https://www.haomeiwen.com/subject/fvvngxtx.html