架子分层问题 - 动态规划详解

📖 问题描述

有 n 个摆件，按顺序摆放在架子上。每个摆件 i 有宽度 w_i 和高度 h_i。

规则：

摆件必须按原顺序分层摆放（不能打乱顺序）
每层总宽度 不超过 W（如果放不下了就换下一层）
层高 = 本层中最高的摆件高度
求架子总高度的最小值（即各层高度之和最小）

💡 本质：将序列切分成若干连续段，每段宽度和 ≤ W，每段代价 = 段内最大高度，求总代价最小值。

🎨 具体例子

假设有 5 个摆件，架子宽度 W = 10：

两种分法对比：
✗ 粗暴分法： [①,②] + [③] + [④,⑤] → 层高 = 5 + 6 + 5 = 16
✓ 最优分法： [①] + [②,③,④] + [⑤] → 层高 = 3 + 6 + 3 = 12 👈

📖 递推方法详解

核心思路：
定义 dp[i] = 前 i 个摆件（1 ~ i）的最小总高度。
最终答案 = dp[n]

递推公式：

dp[i] = min( dp[j-1] + max(h_j, ..., h_i) )
其中 j 从 i 向左枚举，使 w_j + ... + w_i ≤ W

初始化：dp[0] = 0（没有摆件，高度为 0）
划分点 j：从位置 j 到 i 作为同一层，前提是这些摆件宽度和 ≤ W
层高：该层高度 = max(h[j..i])（本层最高摆件）
转移：dp[i] = min(dp[j-1] + 层高)，取所有合法 j 的最小值

实现要点：

外层循环 i = 1 → n，内层 j = i → 1 向左枚举
维护当前段宽度和 sumW，超过 W 就 break
同时维护当前段最大高度 maxH，随 j 左移更新
转移：dp[i] = min(dp[i], dp[j-1] + maxH)
时间复杂度 O(n²)，空间 O(n)

💻 C++ 核心代码

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

// 摆件结构体
struct Item {
    int w;  // 宽度
    int h;  // 高度
};

// 计算架子最小总高度
int minShelfHeight(vector<Item>& items, int W) {
    int n = items.size();
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;  // 没有摆件时高度为 0

    // 1‑based 索引，items[0] 对应摆件 1
    for (int i = 1; i <= n; i++) {
        int sumW = 0;     // 当前层累计宽度
        int maxH = 0;     // 当前层最大高度

        // 从 i 向左枚举 j，尝试将 [j..i] 作为一层
        for (int j = i; j >= 1; j--) {
            sumW += items[j - 1].w;  // 累加宽度
            if (sumW > W) break;      // 超宽，停止

            maxH = max(maxH, items[j - 1].h);  // 更新层高

            // dp[j-1] + 本层层高 → dp[i]
            dp[i] = min(dp[i], dp[j - 1] + maxH);
        }
    }

    return dp[n];  // 前 n 个摆件的最小总高度
}

📚 架子分层问题

📖 问题描述

🎨 具体例子

📖 递推方法详解

💻 C++ 核心代码

✏️ 交互演示

📈 结果

📋 DP 表（dp[i] = 前 i 个摆件最小总高度）

🔍 详细推导步骤