分割整数的实例与代码
来源：9-3 发现重叠子问题 Integer Break
慕标6347362
2018-12-31
你好，老师！我反复听这个例子，都没能理解这个递推关系。可以在这里套入视频中以4的作为例子再解释一下？
在老师代码 memo[i]= max3(memo[i], j * (i - j), j * memo[i - j]); 中的j * (i - j)和j * memo[i - j]分别在图中实例代表哪些数的乘积？尤其为什么j * memo[i - j]可以作为备选项？
class Solution {
private:
int max3(int a, int b, int c) {
return max(a, max(b, c));
}
public:
int integerBreak(int n) {
assert(n >= 2);
// memo[i]表示将数字i分割(至少分割两部分)后得到的最大乘积
vector<int> memo(n + 1, -1);
// 自底向上：所以最小分成1， 1的最大乘积是1，所以1
memo[1] = 1;
for (int i = 2; i <= n; i++)
// 求解memo[i]
for (int j = 1; j <= i - 1; j++)
// j + (i-j)
memo[i]= max3(memo[i], j * (i - j), j * memo[i - j]);
return memo[n];
}
};
int main() {
return 0;
}
谢谢！！！
写回答
1回答
-
理解算法的关键，就是理解算法中的每一个变量，每一个函数的语义。
在这个程序中，memo[x]的语义是：将x分割几个整数的和，他们乘积的最大值。
在这个语义的基础上，对于任意一个数字i，我们将其进行分割：
或者将其拆成两部分，一部分是j的话，另一部分就是i - j，对应j * (i - j)；
或者将其拆分成三个或者三个以上的部分，此时，我们先考虑分割出的一个数字为j，之后，还要对剩下的i-j进行分割。剩下的i - j进行分割后乘积的最大值是memo[i - j]（回顾上面memo的语义！），在加上我们已经分割出的j，所以分割i得到的乘积的最大值，就是 j * memo[i - j]。
看看能否理解？继续加油！新年快乐！：）
132019-01-01
相似问题