Medium

题目描述

给定一个整数 n。

在一次操作中，你可以将整数 x 分解为两个正整数 a 和 b，使得 a + b = x。

这次操作的代价为 a * b。

返回一个整数，表示将整数 n 分解为 n 个 1 所需的最小总代价。

示例 1：

输入：n = 3
输出：3
解释：
一组最优操作为：
x  | a | b | a+b | a*b | 代价
3  | 1 | 2 |  3  |  2  |  2
2  | 1 | 1 |  2  |  1  |  1

因此，最小总代价为 2 + 1 = 3。

示例 2：

输入：n = 4
输出：6
解释：
一组最优操作为：
x  | a | b | a+b | a*b | 代价
4  | 2 | 2 |  4  |  4  |  4
2  | 1 | 1 |  2  |  1  |  1
2  | 1 | 1 |  2  |  1  |  1

因此，最小总代价为 4 + 1 + 1 = 6。

约束条件：

  • 1 <= n <= 500

提示：

  • 使用动态规划或数学方法。
  • 总是将当前整数 x 分解为 1 和 x - 1 是最优的。

解题思路

这道题目要求将整数 n 分解为 n 个 1，每次分解的代价为两个分数的乘积。

数学分析法： 根据题目提示，最优策略是每次都将数字 x 分解为 1 和 x-1。我们可以通过数学归纳法证明这个结论：

  • 对于数字 x，如果分解为 a 和 b（其中 a + b = x），代价为 a * b
  • 当 a = 1, b = x-1 时，代价为 1 * (x-1) = x-1
  • 对于其他分解方式 a = k, b = x-k（其中 1 < k < x-1），代价为 k * (x-k)
  • 可以证明 k * (x-k) ≥ x-1 当 k ≥ 2 时成立

因此，最优分解序列为：n → (1, n-1) → (1, 1, n-2) → ... → (1, 1, ..., 1)

总代价 = (n-1) + (n-2) + ... + 1 = n*(n-1)/2

动态规划法： 也可以使用动态规划来验证这个结论。dp[i] 表示将数字 i 分解为 i 个 1 的最小代价。状态转移方程为： dp[i] = min(dp[a] + dp[b] + a*b) 其中 a + b = i

两种方法都能得到相同的结果，数学分析法更高效。

代码实现

class Solution {
public:
    int minCost(int n) {
        return n * (n - 1) / 2;
    }
};

class Solution:
    def minCost(self, n: int) -> int:
        return n * (n - 1) // 2

public class Solution {
    public int MinCost(int n) {
        return n * (n - 1) / 2;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var minCost = function(n) {
    return Math.floor(n * (n - 1) / 2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数学解法动态规划解法
时间复杂度O(1)O(n³)
空间复杂度O(1)O(n)