Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: dora

状态定义:

dp[i] 表示将整数 i 拆分成 至少两个正整数之和 的最大乘积。

状态转移:
我们枚举拆分方式,把 i 拆成 j + (i-j),然后比较:
(j,dp[j]) 和 (i-j,dp[i-j]) 选择最大值 然后相乘就是 dp[i]

拆成两个数 j 和 i - j,要么直接使用数值本身(比如 j),要么继续拆成更小的部分(用 dp[j])。


Comments

There are no comments at the moment.