聊聊DP入门之整数拆分!
您的位置超橾人人在线免费视频-草莓直播二维码下载手机官网-东方在线影 > 草莓直播二维码下载手机官网 > 阅读资讯文章

聊聊DP入门之整数拆分!

2022-01-13 13:42:47   来源:http://www.bfangel.com   【

 整数拆分

力扣题现在链接:https://leetcode-cn.com/problems/integer-break

给定一个正整数 n,将其拆分为起码两个正整数的和,并使这些整数的乘积最大化。返回你能够获得的最大乘积。

示例 1:

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

示例 2:

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

表明: 你能够倘若 n 不幼于 2 且不大于 58。

思路

望到这道题现在,都会想拆成两个呢,照样三个呢,照样四个....

吾们来望一下如何行使行规来解决。

行态规划

行规五部弯,分析如下:

确定dp数组(dp table)以及下标的含义

dp[i]:分拆数字i,能够得到的最大乘积为dp[i]。

dp[i]的定义讲贯彻整个解题过程,下面哪一步想不懂了,就想想dp[i]原形外示的是啥!

确定递推公式

能够想 dp[i]最大乘积是怎么得到的呢?

其实能够从1遍历j,然后有两栽渠道得到dp[i].

一个是j * (i - j) 直接相乘。

一个是j * dp[i - j],相等于是拆分(i - j),对这个拆分不理解的话,能够回想dp数组的定义。

那有同学问了,j怎么就不拆分呢?

j是从1最先遍历,拆分j的情况,在遍历j的过程中其实都计算过了。那么从1遍历j,比较(i - j) * j和dp[i - j] * j 取最大的。递推公式:dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

也能够这么理解,j * (i - j) 是单纯的把整数拆分为两个数相乘,而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。

倘若定义dp[i - j] * dp[j] 也是默认将一个数强制拆成4份以及4份以上了。

因此递推公式:dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

那么在取最大值的时候,为什么还要比较dp[i]呢?

由于在递推公式推导的过程中,每次计算dp[i],取最大的而已。

dp的初首化

不少同学答该疑心,dp[0] dp[1]答该初首化众少呢?

有的题解里会给出dp[0] = 1,dp[1] = 1的初首化,但注释比较牵强,主要照样由于这么初首化能够把题现在过了。

厉格从dp[i]的定义来说,dp[0] dp[1] 就不该该初首化,也就是异国意义的数值。

拆分0和拆分1的最大乘积是众少?

这是无解的。

这边吾只初首化dp[2] = 1,从dp[i]的定义来说,拆分数字2,得到的最大乘积是1,这个异国任何阻止!

确定遍历挨次

确定遍历挨次,先来望望递归公式:dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

dp[i] 是仰仗 dp[i - j]的状态,因此遍历i肯定是以前向后遍历,先有dp[i - j]再有dp[i]。

枚举j的时候,是从1最先的。i是从3最先,云云dp[i - j]就是dp[2]正益能够经过吾们初首化的数值求出来。

因此遍历挨次为:

for (int i = 3; i <= n ; i++) {     for (int j = 1; j < i - 1; j++) {         dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));     } } 

举例推导dp数组

举例当n为10 的时候,dp数组里的数值,如下:

整数拆分

以上行规五部弯分析完毕,C++代码如下:

class Solution { public:     int integerBreak(int n) {         vector<int> dp(n + 1);         dp[2] = 1;         for (int i = 3; i <= n ; i++) {             for (int j = 1; j < i - 1; j++) {                 dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));             }         }         return dp[n];     } }; 
时间复杂度: 空间复杂度: 贪心

本题也能够用贪心,每次拆成n个3,倘若剩下是4,则保留4,然后相乘,但是这个结论必要数学表明其相符理性!

吾异国表明,而是直接用了结论。感有趣的同学能够本身再往钻研钻研数学表明哈。

给出吾的C++代码如下:

class Solution { public:     int integerBreak(int n) {         if (n == 2) return 1;         if (n == 3) return 2;         if (n == 4) return 4;         int result = 1;         while (n > 4) {             result *= 3;             n -= 3;         }         result *= n;         return result;     } }; 

时间复杂度:

空间复杂度:

总结

本题掌握其行规的手段,就能够了,贪心的解法实在浅易,但必要有数学表明,倘若能自圆其说也是能够的。

其实这道题方针递推公式并不益想,而且初首化的地方也很有讲究,吾在写本题的时候一路先写的代码是云云的:

class Solution { public:     int integerBreak(int n) {         if (n <= 3) return 1 * (n - 1);         vector<int> dp(n + 1, 0);         dp[1] = 1;         dp[2] = 2;         dp[3] = 3;         for (int i = 4; i <= n ; i++) {             for (int j = 1; j < i - 1; j++) {                 dp[i] = max(dp[i], dp[i - j] * dp[j]);             }         }         return dp[n];     } }; 
这个代码也是能够过的!

在注释递推公式的时候,也能够注释通,dp[i] 就等于 拆解i - j的最大乘积 * 拆解j的最大乘积。望首来没毛病!

但是在注释初首化的时候,就发现自相矛盾了,dp[1]为什么肯定是1呢?按照dp[i]的定义,dp[2]也不该该是2啊。

但倘若递归公式是 dp[i] = max(dp[i], dp[i - j] * dp[j]);,就肯定要这么初首化。递推公式没毛病,但初首化注释不通!

固然代码在初首位置有一个判定if (n <= 3) return 1 * (n - 1);,保证n<=3 效果是切确的,但代码后面又要给dp[1]赋值1 和 dp[2] 赋值 2,这其实就是自相矛盾的代码,违背了dp[i]的定义!

吾举这个例子,其实就说做题的厉谨性,上面这个代码也能够AC,大体上一望相通也异国毛病,递推公式也说得以前,但是仅仅是碰巧过了而已。

其他说话版本

Java

class Solution {     public int integerBreak(int n) {         //dp[i]为正整数i拆分效果的最大乘积         int[] dp = new int[n+1];         dp[2] = 1;         for (int i = 3; i <= n; ++i) {             for (int j = 1; j < i - 1; ++j) {                 //j*(i-j)代外把i拆分为j和i-j两个数相乘                 //j*dp[i-j]代外把i拆分成j和不息把(i-j)这个数拆分,取(i-j)拆分效果中的最大乘积与j相乘                 dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));             }         }         return dp[n];     } } 

Python

class Solution:     def integerBreak(self, n: int) -> int:         dp = [0] * (n + 1)         dp[2] = 1         for i in range(3, n + 1):             # 倘若对正整数 i 拆分出的第一个正整数是 j(1 <= j < i),则有以下两栽方案:             # 1) 将 i 拆分成 j 和 i−j 的和,且 i−j 不再拆分成众个正整数,此时的乘积是 j * (i-j)             # 2) 将 i 拆分成 j 和 i−j 的和,且 i−j 不息拆分成众个正整数,此时的乘积是 j * dp[i-j]             for j in range(1, i - 1):                 dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))         return dp[n] 

Go

func integerBreak(n int) int {     /**     行态五部弯     1.确定dp下标及其含义     2.确定递推公式     3.确定dp初首化     4.确定遍历挨次     5.打印dp     **/     dp:=make([]int,n+1)     dp[1]=1     dp[2]=1     for i:=3;i<n+1;i++{         for j:=1;j<i-1;j++{ // i能够差分为i-j和j。由于必要最大值,故必要经过j遍历一切存在的值,取其中最大的值行为现在i的最大值,在求最大值的时候,一个是j与i-j相乘,一个是j与dp[i-j].             dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]))         }     }     return dp[n] } func max(a,b int) int{     if a>b{         return a     }     return b } 

Javascript

var integerBreak = function(n) {     let dp = new Array(n + 1).fill(0)     dp[2] = 1      for(let i = 3; i <= n; i++) {         for(let j = 1; j < i; j++) {             dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j)         }     }     return dp[n] }; 

【编辑选举】

鸿蒙官方战略配相符共建——HarmonyOS技术社区 Kubernetes容器平台架构解读 支付宝 App 集五福版发布:福相伴,五福,马上到! Windows 11 22526新版修复大量题目!新特性抢先望 WiFi7有众强?比WiFi6高三倍,速度快如飞 Python再获年度编程说话,微柔或成最大赢家
Tags:聊聊,入门,之,整数,拆分,整数,拆分,力,扣题,  
请文明参与讨论,禁止漫骂攻击。 用户名: 密码: 匿名:

合作伙伴/友情链接