## 一、数字三角形最大路径和

### 问题描述

给定一个数字三角形，从顶部到底部走一条路径，每一步只能走左下或右下，求路径上数字之和的最大值。不需要输出具体路径。

### 示例输入

text

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

### 动态规划解法

从底部向上递推：

dp[i][j]=triangle[i][j]+max⁡(dp[i+1][j],dp[i+1][j+1])dp[i][j]=triangle[i][j]+max(dp[i+1][j],dp[i+1][j+1])

- `dp[i][j]` 表示从位置 `(i, j)` 到底部的最大路径和。
    
- 最后一行直接初始化为三角形最后一行。
    
- 最终答案就是 `dp[0][0]`。
    

### 空间优化

可以只用一个一维数组 `dp`，初始化为三角形最后一行，然后从倒数第二行向上更新：

python

dp[j] = triangle[i][j] + max(dp[j], dp[j+1])

### 复杂度

- 时间复杂度：O(n 2)O(n 2)
    
- 空间复杂度：O(n 2)O(n 2)，优化后为 O(n)O(n)
    

### 示例结果

输入上面的三角形，输出最大路径和为：

text

30

---

# 动态规划与贪心综合题

## 二、磁带最优存储问题

### 问题描述

有 nn 个程序需要存储在磁带上，每个程序有长度 lili​ 和读取概率 pipi​。目标是安排程序顺序，使平均读取时间最小。

平均读取时间定义为：

∑i=1 n∑k=1 ipikliki=1∑n​k=1∑i​pik​​lik​​

也就是说，越靠前的程序，其读取时间会被后面更多程序“重复计算”，所以希望概率高、长度短的程序尽量靠前。

### 贪心策略

按照以下比值从大到小排序：

pilili​pi​​

即单位长度贡献概率越高的程序越靠前。

### 伪代码

plaintext

FUNCTION optimal_storage_order(n, programs):
    FOR i = 0 TO n-1:
        length, prob = programs[i]
        programs[i].ratio = prob / length
    SORT programs BY ratio DESCENDING
    total_time = 0
    prefix_sum = 0
    FOR i = 0 TO n-1:
        length, prob = programs[i]
        prefix_sum += prob * length
        total_time += prefix_sum
    RETURN programs, total_time

### 复杂度

- 时间复杂度：O(nlog⁡n)O(nlogn)
    
- 空间复杂度：O(n)O(n)
    

### 关于概率的说明

题目中可能出现两种说法：

1. 直接给定概率 pipi​，且 ∑pi=1∑pi​=1。
    
2. 输入的是权重 bibi​，真实概率为：
    

pi=bi∑j=1 nbjpi​=∑j=1 n​bj​bi​​

如果题目写成：

pk=ak∑aipk​=∑ai​ak​​

那可能是笔误。更合理的解释是：输入的 `b_k` 是概率权重，真实概率由权重归一化得到，而不是由长度决定。否则问题会退化成只按长度排序，失去概率的独立意义。

### 示例

输入：

text

3
5 10
10 5
2 20

按 pi/lipi​/li​ 排序后，最优顺序为：

text

程序 3 → 程序 1 → 程序 2

最小平均时间为：

text

270

---

## 三、为什么说“局部最优能构成全局最优”和“最优子结构”？

这是在解释贪心算法正确性时常用的两个性质。

### 1. 贪心选择性质

每一步都选择当前看起来最优的那个程序，也就是 pi/lipi​/li​ 最大的程序放在前面。可以证明：存在一个最优解，它的第一个程序就是当前贪心选出的程序。因此，局部最优选择不会破坏全局最优。

### 2. 最优子结构

当我们选好第一个程序后，剩下的问题仍然是“把剩余程序按某种顺序排列，使平均读取时间最小”，和原问题形式完全一样。也就是说，原问题的最优解包含子问题的最优解。因此可以继续用同样的贪心策略处理剩余程序。

这两条合在一起，说明按 pi/lipi​/li​ 从大到小排序得到的顺序就是全局最优顺序。

---

## 四、整体总结

|问题|核心方法|关键公式|复杂度|
|---|---|---|---|
|数字三角形最大路径和|动态规划，自底向上|dp[i][j]=a[i][j]+max⁡(dp[i+1][j],dp[i+1][j+1])dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1])|O(n 2)O(n 2)，空间可优化到 O(n)O(n)|
|磁带最优存储|贪心排序|按 pi/lipi​/li​ 从大到小排序|O(nlog⁡n)O(nlogn)|
|贪心正确性|贪心选择性质 + 最优子结构|局部最优可扩展为全局最优|—|

简单说：

- 数字三角形用**动态规划**从下往上推。
    
- 磁带存储用**贪心算法**按“概率/长度”排序。
    
- 贪心之所以正确，是因为它满足**贪心选择性质**和**最优子结构**。