3010. Divide an Array Into Subarrays With Minimum Cost I

📘 題目敘述

給你一個長度為 n 的整數陣列 nums。

定義一個陣列的 代價（cost） 為它的 第一個元素。

例如：

[1,2,3] 的代價是 1
[3,4,1] 的代價是 3

你需要把 nums 切成 3 個連續且互不重疊 的子陣列（也就是用兩個切點把陣列分成三段，每段都要非空）。

請回傳這三個子陣列的 代價總和最小值。

條件限制

3 <= n <= 50
1 <= nums[i] <= 50

🧠 解題思路

這題切成三段後，三個子陣列的代價會是：

第一段的代價一定是 nums[0]（因為第一段一定從 index 0 開始）
第二段的代價是「第二段起點」那個位置的值
第三段的代價是「第三段起點」那個位置的值

所以整題其實等價於：

固定一定要拿 nums[0]，然後再從 nums[1..] 裡挑兩個不同位置當切點起點，讓它們的值總和最小。

因此我只要在 nums[1] ~ nums[n-1] 中找出 最小值與第二小值，答案就是： nums[0] + 最小值 + 第二小值

所有變數

m：str1 長度（你的程式中用 m = str1.size()；此題用不到）
n：陣列 nums 的長度（你的程式中 int n = nums.size();）
fst：在 nums[1..] 中掃到的「最小值」
snd：在 nums[1..] 中掃到的「第二小值」
i：掃描用索引（從 1 開始，因為 nums[0] 已固定必選）

你把 fst 初始設成 70、snd 設成 100，是利用題目 nums[i] <= 50，確保一開始一定會被更新（也可以用 INT_MAX 更通用）。

🪜 主要流程步驟

1. 固定第一段代價

第一段一定從 0 開始，所以代價必定包含 nums[0]
之後只需要處理「剩下兩段的起點值怎麼選最小」

2. 在 `nums[1..]` 找最小與次小

我從 i = 1 掃到結尾，維護兩個值：

如果 nums[i] < fst
- 代表出現新的最小值
- 原本的 fst 會被擠到第二小，所以：
- snd = fst
- fst = nums[i]
否則如果 nums[i] < snd
- 代表它介於最小與第二小之間
- 更新：snd = nums[i]

3. 回傳最小總代價

最後答案就是：

nums[0] + fst + snd

因為 fst、snd 對應到第二段、第三段的起點值（兩個切點），能讓總和最小。

💻 程式碼實作

class Solution {
public:
    int minimumCost(vector<int>& nums) {
        int fst = 70, snd = 100;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < fst) {
                snd = fst;
                fst = nums[i];
            } else if (nums[i] < snd) {
                snd = nums[i];
            }
        }
        return nums[0] + fst + snd;
    }
};

🔗 題目連結

https://leetcode.com/problems/divide-an-array-into-subarrays-with-minimum-cost-i/