力扣343. 整数拆分（动态规划）

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

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

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

 

动态规划

四步走：

 

1、确定状态

1.1、最后一步：

对于的正整数 n，当 n≥2 时，可以拆分成至少两个正整数的和。令 k 是拆分出的第一个正整数，则剩下的部分是 n−k，n−k 可以不继续拆分，或者继续拆分成至少两个正整数的和

1.2、子问题：

n−k拆分，获得的最大乘积。

创建数组 f，其中 f[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积。

2、转移方程

“至少”两个字包含两种情况：

将n分解成两个数: (i-j) * j   ， 对应不继续拆分情况将n分解成两个以上的数：f(i-j) * j   ， 对应继续拆分情况

3、初始条件和边界情况

特别地，0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此f0]=0,f[1]=0。

4、计算顺序

从小到大

// // main.cpp // 343integerBreak // // Created by MXQ on 2020/10/21. // #include <iostream> #include<vector> using namespace std; class Solution { public: int integerBreak(int n) { if(n==0)return 0; vector<int>f(n+1); f[0]=0; f[1]=1; for (int i=2; i<=n; i++) { int max=INT_MIN; for (int j=1; j<i; j++) { //i-j继续拆分 f[i]=f[i-j]*j; if (f[i]>max) { max=f[i]; } //i-j不继续拆分 f[i]=(i-j)*j; if (f[i]>max) { max=f[i]; } } f[i]=max; } return f[n]; } }; int main(int argc, const char * argv[]) { // insert code here... Solution s; auto result =s.integerBreak(10); std::cout << result<<endl; std::cout << "Hello, World!\n"; return 0; }