-
-
分析
-
状态表示：
· dp[i] 表示整数 i 拆分乘积的最大值。
-
转移方程：
· 对于每个数字 i 都进行一遍循环，计算 (i - j) * j，(j <= i - 1)，并求其与 dp[i]，dp[i - j] * j 的最大值，即：dp[i] = max(dp[i]，(i - j) * j，dp[i - j] * j)
· 与 dp[i - j] * j 比较是因为 i - j 可能小于 i - j 拆分的乘积。
-
边界：
· 输入的整数 n 大于等于 2，考虑到会拆分成类似 (i - 1) * 1 等类型，故dp[1] = 1
-
-
实现
class Solution { public: int integerBreak(int n) { int dp[n + 1]; memset(dp, -1, sizeof(dp)); dp[1] = 1; for(int i = 2; i <= n; ++i) { for(int j = 1; j <= i - 1; ++j) { dp[i] = max(dp[i], dp[i - j] * j); dp[i] = max(dp[i], (i - j) * j); } } return dp[n]; } }; -
小结
- 确定状态转移的方式：想求dp[i]，应先求dp[i - j]，(j <= i - 1)
- 确定状态转移方程：明确拆分时的可能乘积，本题有两个 (i - j) * j 和 j * dp[i - j]
- 确定边界
leetcode 343. 整数拆分：动态规划(c++)
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 回溯算法 回溯法：也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并...
- 计算机二级C语言上机题库（南开版） 1.m个人的成绩存放在score数组中，请编写函数fun,它的功能是：将低于平...
