【力扣刷题】整数拆分（动态规划）

天寒雨落

发布于 2022-11-20 11:11:30

4960

发布于 2022-11-20 11:11:30

文章被收录于专栏：编程学习之路

个人简历：全栈领域新星博主，万粉博主、帮助初学者入门，记录自己的学习过程

个人主页：天寒雨落的博客_CSDN博客-C,CSDN竞赛,python领域博主

热门专栏：初学者入门C语言_天寒雨落的博客-CSDN博客

动态规划

其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，经分解得到子问题往往不是互相独立的，举个简单的例子：你知道两个1相加等于2，问你三个1相加你是拿前面的两个1相加的结果加上1呢，还是再用1+1+1，你肯定会用前面的那种方法对吧，这就是动态规划，（1+1）就是（1+1+1）的子问题，且并不是相互独立，你得到了（1+1）就好得到（1+1+1）了

整数拆分

题目

给定一个正整数 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。

提示:

2 <= n <= 58

思路

对于正整数 n，当 n≥2 时，可以拆分成至少两个正整数的和。令 x 是拆分出的第一个正整数（取值范围为1~（n-1）），则剩下的部分是 n-x

n-x有两种情况：

1.不可以继续拆分，那么乘积就是x*(n-x)

2.可以继续拆分成至少两个正整数的和,那么乘积就是x*((n-x)的乘积最大化)，将子问题求的解即将2到n的所有乘积最大化存入数组dp[n]中，那么乘积就是x*dp[n-x]

用for循环按照上面的方法求2~n的乘积最大化，比如：

求2的乘积最大化：

不可以继续拆分，乘积是1*(2-1)为1

求3的乘积最大化：

可以拆分为1和2，2不拆分的乘积为2，拆分的乘积为1*dp[3-1]也就是1，取不拆分的乘积和拆分的乘积的最大值为2

求4的乘积最大化：

可以拆分为1和3,3不拆分的乘积为3，拆分的乘积为1*dp[4-1]也就是2，取不拆分的乘积和拆分的乘积的最大值为3

可以拆分为2和2,2不拆分的乘积为4，拆分的乘积为2*dp[4-2]也就是2，取不拆分的乘积和拆分的乘积的最大值为4

这和上面两个不一样，它可以拆分为1和3,2和2两种情况，所以要求1和3,2和2之间的最大值为4

依次类推......

因为求最大值的功能经常使用，使用用三目运算符？：写个求最大值的函数Max（）

由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。

代码

#include <stdio.h>
int Max(int i, int j);

int main() {
	int n;
	printf("n=");
	scanf("%d", &n);
	int dp[n] = {0, 0};

	for (int i = 2; i <= n; i++) {
		int max = 0;

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

		dp[i] = max;
	}

	printf("%d", dp[n]);
	return 0;
}

int Max(int i, int j) {
	return i > j ? i : j;
}