2547.拆分数组的最小代价

链接：2547.拆分数组的最小代价
难度：Hard
标签：数组、哈希表、动态规划、计数
简介：找出并返回拆分 nums 的所有可行方案中的最小代价。

题解 1 - cpp

• 编辑时间：2023-01-22
• 执行用时：1576ms
• 内存消耗：306MB
• 编程语言：cpp
• 解法介绍：dp判断每个数组作为结尾时的最小开销。

class Solution {
 public:
     int minCost(vector<int>& nums, int k) {
         int n = nums.size();
         vector<int> dp(n + 1, 0x3f3f3f3f);
         dp[0] = 0;
         for (int i = 1; i <= n; i++) {
             unordered_map<int, int> m;
             int sum = 0;
             for (int j = i; j >= 1; j--) {
                 m[nums[j - 1]]++;
                 if (m[nums[j - 1]] == 2) sum += 2;
                 else if (m[nums[j - 1]] > 2) sum += 1;
                 dp[i] = min(dp[i], dp[j - 1] + k + sum);
             }
         }
         return dp[n];
     }
 };

题解 2 - python

• 编辑时间：2023-01-22
• 执行用时：5948ms
• 内存消耗：15.1MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
def minCost(self, nums: List[int], k: int) -> int:
    n = len(nums)
    dp = [0x3f3f3f3f for _ in range(n + 1)]
    dp[0] = 0
    for i in range(1, n + 1):
        m = Counter()
        sum = 0
        for j in range(i, 0, -1):
            num = nums[j-1]
            m[num] += 1
            if m[num] == 2:
                sum += 2
            elif m[num] > 2:
                sum += 1
            dp[i] = min(dp[i], dp[j - 1] + k + sum)
    return dp[n]

题解 3 - rust

• 编辑时间：2023-01-22
• 执行用时：312ms
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn min_cost(nums: Vec<i32>, k: i32) -> i32 {
        use std::collections::HashMap;
        let n = nums.len();
        let mut dp = vec![0x3f3f3f3f;n + 1];
        dp[0] = 0;
        for i in 1..=n {
            let mut m = HashMap::<i32,i32>::new();
            let mut sum = 0;
            let mut j = i;
            while j >= 1 {
                let num = nums[j-1];
                let val = m.entry(num).or_insert(0);
                *val += 1;
                if *val == 2 {
                    sum += 2;
                } else if *val > 2 {
                    sum += 1;
                }
                dp[i] = dp[i].min(dp[j - 1] + k + sum);
                j-=1;
            }
        }
        dp[n]
    }
}