Problem: 343. 整数拆分
该题目可以抽象成动态规划中的爬楼梯模型,将整数的拆分类比为上台阶:
1.每个阶段可以从整数中划分出1、2、…k的一个整数
2.int dp[n + 1] dp[i]表示为i的整数划分的最大乘积
3.到达第i个状态,那上一步只能是划分了1、2、…、i,也就是从状态i-1, i-2, i-3, 、、、、0转换过来。dp[i]的值也是由dp[i - 1], dp[i - 2], dp[i - 3] … dp[0]推到出来。
4.dp[i] = max(1dp[i - 1], 2dp[i - 2], 3dp[i - 3], …idp[0])我们按爬楼梯模型来想,假设当前在第i层台阶则第i层台阶可以i-1, i-2, …0层台阶走来,即从i-1走到i层台阶需要走1步,i-2层台阶走到第i层台阶需要走2步…
1.特殊处理数字1,2,3(当数字大于等于4时其划分的乘积是大于等于该整形数的)
2.定义int[] dp = new int[n + 1];dp[i]表示为i的整数划分的最大乘积
3.初始dp[0] = 1按爬楼梯模型来看表示从地面可以一步直接跨到第n层台阶
4.从1开始双层循环,并且开始比较若**dp[i] < j * dp[i - j]**则更新dp[i]为j * dp[i - j];最后返回dp[n]
时间复杂度:
O ( n 2 ) O(n^2) O(n2);其中 n n n为给定整形数的大小
空间复杂度:
O ( n ) O(n) O(n)
class Solution {
public:
int integerBreak(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 1;
}
if (n == 3) {
return 2;
}
vector<int> dp(n + 1);
dp[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
if (dp[i] < j * dp[i - j]) {
dp[i] = j * dp[i - j];
}
}
}
return dp[n];
}
};