Keshawn_lu's Blog

Leetcode 343. 整数拆分

动态规划
字数统计: 335阅读时长: 1 min
2020/07/30 Share

题目简介：

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

示例 1:

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

示例 2:

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

说明: 你可以假设 n 不小于 2 且不大于 58。

思路：

动态规划，dp[i]代表正整数i，拆分为至少两个正整数的和，并使这些整数的乘积最大化，可以获得的最大乘积。

所以对于一个正整数i >= 2，乘积的最大值存在以下两种情况：

  1. 将i分为j, i - j，并且i - j不再分离，此时乘积为j * (i - j)。
  2. 将i分为j, i - j，并把i - j继续分离，此时乘积为j * dp[i - j]。

所以我们只要遍历j，从1 ~ i - 1，在过程中记录最大值，最后赋值给dp[i]即可。

最后返回dp[n]即可。

tip:

  • dp[0] = dp[1] = 0。(不可分离)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int integerBreak(int n) {

        vector<int> dp(n + 1, 0);

        for(int i = 2; i <= n; i++){

            int temp = 0;
            for(int j = 1; j < i; j++){

                temp = max( temp, max(j * (i - j), j * dp[i - j]) );
            }

            dp[i] = temp;
        }

        return dp[n];

    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网