动态规划---整数拆分 Posted on 2021-08-31 00:00:00 2021-08-31 00:00:00 by Author 摘要 随机给定一个数，把这个数拆分成大于等于2个整数的和，并且使得拆分后组合的乘积最大，你能找出拆分该数后的组合最大乘积是多少吗？？？ # 动态规划---整数拆分 1. 题目描述 - 给定一个正整数 *n*，将其拆分为**至少**两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 2. 示例描述 - 示例一 ```java 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 ``` - 示例二 ```java 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 ``` 3. 解题思路 - 首先对于这道题而言，看完题目之后我就有点懵逼，不知如何下手，因为在我脑中一直有两个问题缠绕着我，第一问题就是，对于数字k,怎么存储多个整数，使其和为k。第二个问题就是，对于数字k来说，组成k的组合有多个，那么怎么找出这些组合中乘积最大的值尼。 - 说实话这道题目最终我自己也没想出来，最后还是参考了公众号<代码随想录>Carl哥的解题思路，才明白解这道题的实现方式，同时也解开了我之前的困扰。这里我就以我理解的方式来描述Carl哥解题的思路。首先定义一个数组，数组下标代表数字k,该位置存储的是数字和为k的最大乘积。对于每个数来说，和为该数的组合方式有多种，并且这些组合的乘积也各不相同，那么这里可以把一个数拆成两个数，即k=j+(k-j),对于k这个数这些拆分的数字乘积是j*dp[k-j]和 j *(k-j)这两种形式(定义的数组名称为dp),为什么有两种形式尼，因为我们要求的是组成k的组合乘积最大的值，那么对于数字K=j+(K-j)来说，他乘积有 j* *(k-j) ，同时对于(k-j）这个数字来说其又有组成这个数的最大乘积，我们要比较这两者与j乘积的最大值，这也才能保证组成数字k，其最大乘积最大。这里也同时也消除了我的一个困扰，及就是对于数字k来说，怎么找到和为K的多个组合的问题，其隐藏在 j * dp[k-j] 这里,为什么这么说尼，因为dp[k-j]存储的是数字(k-j)其组合乘积的最大值。那么j* dp[k-j]，就间接隐藏了组成k-j这个数字的多个组合与j的乘积了。即为不需要j与组成(k-j)多个组合每一个组合进行连续相乘了，因为dp[k-j]就存储了组成(k-j)这个数其组合中的最大的乘积了。同时对于k来说，组成数字k有多种组合，那么这里j可以取到的范围是从1到数字k，对于每一次k的取值都找到此时组合的最大值，直到j遍历完整个范围后，就能找出组成数字k并且这个组合乘积最大值了。 - 以上就是我个人的理解，然后主要的递推公式即为:dp[i] = Math.max(Math.max(j * dp[i - j], j * (i - j)), dp[i]);每一个数字i,比较 (i-j) * j 与 j* dp[i-j]的最大值，然后找出本次最大值之后，在和之前已经组合成i的最大乘积值比较，直到j遍历完整个取值范围内后，dp[i]中就存储这组成i并且组合乘积最大的值了。 - 以上是我个人理解，具体代码如下。 4. 代码示例 ```java public int integerBreak(int n) { //初始化dp数组 int[] dp = new int[n + 1]; //对于数组0，和为0并且最大乘积为0 dp[0] = 0; //对于1也是 dp[1] = 0; //对于2来说(1+1=2)满足情况 dp[2] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { //对于其他数来说，dp的递推公式如下 //对于数子i来说，要使其乘积最大，并且多个数相加的和为i //那么我们分别比较比该数字小的数，因为比该数字小的数才能组成和为i的数 //对于数字i来说(i=j+(i-j),其最大的和为j*dp[i-j](dp[i-j]存储的是(i-j)这个数的最大和乘积) //之后要使其乘积最大，那么j*dp[i-j]不一定比(j*(i-j))的乘积大，所以比较这两个值最大的和之前已经找出dp[i]最大值进行比较 //遍历完整循环之后dp[i]中就存储着数字和为i，并且乘积最大的值了。 dp[i] = Math.max(Math.max(j * dp[i - j], j * (i - j)), dp[i]); } } //返回该和为n，多个数字连续乘积最大的值。 return dp[n]; } ```
{{ item.content }}
{{ child.content }}