美文网首页LeetCode题解
算法练习:整数拆分(动态规划)

算法练习:整数拆分(动态规划)

作者: cofbro | 来源:发表于2022-05-30 21:49 被阅读0次

    一.前言

    最近一直在了解动态规划,这是LeetCode上面的一道动规的题。

    343. 整数拆分

    给定一个正整数 n ,将其拆分为 k正整数 的和( k >= 2 ),并使这些整数的乘积最大化。
    返回 你可以获得的最大乘积

    示例1:

    输入: n = 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1。

    示例2:

    输入: n = 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。


    二.思路

    说到动态规划,我认为最重要的就是确定自己的 dp数组 的含义,其次就是 递推公式 了。

    • 确定 dp[i] 的含义

    我们重新浏览一遍题,给定一个正整数 n ,需要将它分成若干个整数,返回最大的乘积。因此我们可以定义 dp[i] 表示每个正整数拆分为若干个正整数所对应的最大乘积,若要确定 dp[i] 的值,我们可以根据 dp[i] 以前的元素进行运算从而得到最大的
    dp[i] 的值。

    • 确定 dp[i] 的值

    dp[i] 的值是由两种方式来共同确定的。
    第一,dp[i] = dp[i - j] * j 其中 i 代表外层循环, j 代表内层循环,j1 开始逐个求出 dp[i] ,最后取最大值。
    第二,dp[i] = (i - j) * j,同上,也是取最大值。上面那种方式是将 i 分成了 n(n > 2)。而这种方式是将 i 分成了n(n = 2)

    • 确定递推公式

    其实到这里,递推公式大致样式也就出来了:
    dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, (i - j) * j)) ,那么可能会有人问为什么还要比较一次 dp[i] 呢?因为我们内层循环中一周后,会算出很多 dp[i] ,我们只需要保存最大的 dp[i]


    三.代码

    class Solution {
        public int integerBreak(int n) {
            int[] dp = new int[n + 1];
            //dp[2]对应的值应该是1,而dp[2]之前的元素在此问题中无实际意义,因此无需初始化
            dp[2] = 1;
            for(int i = 3; i <= n; i++){
                for(int j = 1; j <= i - j; j++){
                    dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, j * (i - j)));
                }
            }
            return dp[n];
        }
    }
    

    时间复杂度 O(n^2)

    • 题外话
      这道题用动态规划的话时间复杂度似乎有点高,其实这道题可以用数学方法来写的,这里用到一个结论:当整数 n 尽可能地等分为 3时乘积最大。如果感兴趣的同学可以去证明一下。
    class Solution {
        public int integerBreak(int n) {
            if(n <= 3) return n - 1;
            int a = n / 3, b = n % 3;
            //当 n 分刚好能分成若干个 3 时
            if(b == 0) return (int)Math.pow(3, a);
            //当 n 尽可能分成 3 时,余出一个 1 
            if(b == 1) return (int)Math.pow(3, a - 1) * 4;
            //当 n 尽可能分成 3 时,余出一个 2
            return (int)Math.pow(3, a) * 2;
        }
    }
    

    时间复杂度:O(1)

    相关文章

      网友评论

        本文标题:算法练习:整数拆分(动态规划)

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