复杂逻辑注释

import java.util.concurrent.locks.ReentrantLock; import java.util.HashMap; import java.util.Map;

public class LRUCache<K,V> { private class Node { K k; V v; Node prev, next; Node(K k, V v){ this.k = k; this.v = v; } }

private final int capacity;
// HashMap 本身不是线程安全的，但本实现使用同一把独占锁串行化对 map 与链表的所有访问，
// 因而无需 ConcurrentHashMap；同时保证“哈希索引 + 双向链表指针”这两个结构上的复合更新具有原子性（逻辑原子）。
private final Map<K,Node> map = new HashMap<>();
// 头尾哨兵节点：避免边界判空，指针操作固定为四步，降低并发条件下的分支复杂度
private final Node head = new Node(null, null);
private final Node tail = new Node(null, null);
// 单把 ReentrantLock 作为“全局互斥”：将 map 与双向链表的修改纳入同一临界区，维持 LRU 不变式的一致性。
// 注意：默认非公平锁，吞吐更高；需要可选公平性时可改为 new ReentrantLock(true)。
private final ReentrantLock lock = new ReentrantLock();

public LRUCache(int capacity){
    this.capacity = capacity;
    head.next = tail; tail.prev = head;
}

// 注意：以下两个链表操作均假定调用方已持有 lock。
// 在并发语境下，不暴露 Node 引用给外部线程，避免指针被并发篡改。
private void addFirst(Node n){
    // 将 n 插到表头，四步指针更新需在同一临界区内完成，避免中途被打断造成断链
    n.next = head.next; n.prev = head;
    head.next.prev = n; head.next = n;
}

private void remove(Node n){
    // 从链表摘除节点，同样是 O(1) 的四步操作；在锁保护下，不会与其他 remove/addFirst 交错
    n.prev.next = n.next;
    n.next.prev = n.prev;
    // 可选：n.prev = n.next = null; 有助于 GC 与调试，但非必要
}

public V get(K key){
    // get 虽是“读”语义，但会改变访问顺序（移动到表头），因此必须获取独占锁；
    // 使用读写锁也无法提升并发度，因为读路径同样是“写”操作。
    lock.lock();
    try {
        // 在锁内访问 HashMap，避免并发结构性修改引发的不一致
        Node n = map.get(key);
        if (n == null) return null;
        // 命中后移动到表头：对链表的两次操作（remove + addFirst）与对 map 的读取共同处于同一临界区，
        // 保证在任何时刻，(map 中存在 key) 与 (链表中存在对应节点且位置正确) 这一不变式保持一致。
        remove(n); addFirst(n);
        // 通过锁的释放建立“happens-before”，确保值对后续线程可见；Node 字段无需使用 volatile。
        return n.v;
    } finally { 
        // try/finally 确保异常或提前返回也能正确释放锁，避免死锁
        lock.unlock(); 
    }
}

public void put(K key, V value){
    // put 涉及 map 与链表的复合更新与可能的淘汰，必须持有同一把锁，形成原子批处理
    lock.lock();
    try {
        Node n = map.get(key);
        if (n != null){
            // 更新已有键：写值 + 移动到表头必须在同一临界区，防止被其他线程插入的并发更新打乱顺序
            n.v = value;
            remove(n); addFirst(n);
            return;
        }
        // 插入新键：构造节点后再统一注册到 map 与链表，保持两者同步
        Node nn = new Node(key, value);
        map.put(key, nn);
        addFirst(nn);
        // 超容淘汰：注意“先从链表摘除尾节点，再从 map 删除键”，两步在同一锁内，
        // 从而保证对外表现为单一原子动作；其他线程不会在两者不同步时观察到“幽灵”条目。
        if (map.size() > capacity){
            Node lru = tail.prev; // 尾前为最久未使用节点
            remove(lru);
            map.remove(lru.k);
        }
    } finally { 
        lock.unlock(); 
    }
}

// 并发设计补充：
// 1) 锁粒度：本实现采用“粗粒度单锁”覆盖 map 与链表，优点是简单且严格维持 LRU 全局顺序一致性；
//    缺点是在高并发场景有竞争。若要细化：
//    - 分段锁/分片 LRU（多个小缓存各自加锁）能提高并发，但 LRU 只在分片内全局不再严格。
//    - 将 map 用 ConcurrentHashMap 并不能省去链表的互斥，因为顺序维护仍需单点串行化。
//    - 若追求高吞吐，可采用近似 LRU（如 Window-TinyLFU、采样淘汰）以减少全局串行区。
// 2) 可见性与原子性：ReentrantLock 的解锁对后续加锁线程建立 happens-before，保证值与指针变更的可见；
//    “原子性”指逻辑层面：map/链表的复合变更要么全部生效、要么全部不生效。
// 3) 死锁避免：仅使用一把锁且不发生锁顺序反转，不会形成死锁；务必保持所有内部辅助方法在持锁条件下调用。

public static void main(String[] args){
    LRUCache<Integer, String> cache = new LRUCache<>(2);
    cache.put(1, "A");
    cache.put(2, "B");
    cache.get(1);
    cache.put(3, "C"); // 淘汰key=2
    System.out.println(cache.get(2)); // null
    System.out.println(cache.get(1)); // A
    System.out.println(cache.get(3)); // C
}

}

from typing import List

def min_merge_cost(nums: List[int]) -> int: """ 典型区间 DP（石子合并）： - 状态：dp[l][r] 表示把闭区间 [l..r] 合并为一堆的最小代价。 - 转移：最后一次合并一定把 [l..r] 切成两段 [l..k] 和 [k+1..r]， 先分别合并成两堆，再把这两堆合并。两堆相加的代价等于区间 [l..r] 的元素和。 因此： dp[l][r] = min_{k in [l..r-1]} dp[l][k] + dp[k+1][r] + sum(l..r) - 时间复杂度 O(n^3)，空间 O(n^2)；若不做前缀和优化，sum(l..r) 每次 O(r-l+1)，总复杂度会退化为 O(n^4)。 """ n = len(nums) if n <= 1: return 0

# 前缀和：prefix[i] = nums[0..i-1] 的和，prefix[0] = 0
# 这样任意闭区间和 sum(l..r) = prefix[r+1] - prefix[l] 可 O(1) 查询，
# 用于为转移方程中的 “合并两堆的代价 = 区间总和” 提供快速求值。
prefix = [0] * (n + 1)
for i, x in enumerate(nums, 1):
    prefix[i] = prefix[i - 1] + x

def range_sum(l: int, r: int) -> int:
    # 闭区间 [l..r] 的和：prefix[r+1] - prefix[l]
    return prefix[r + 1] - prefix[l]

# dp[l][r] 表示将 [l..r] 合并成一堆的最小代价
dp = [[0] * n for _ in range(n)]
# 长度为 1 的区间已是单堆，代价为 0，已在初始化中体现

# 按区间长度从小到大枚举，保证子问题 [l..k]、[k+1..r] 已经计算
for length in range(2, n + 1):          # 枚举区间长度
    for l in range(0, n - length + 1):  # 枚举左端点
        r = l + length - 1              # 计算右端点
        best = float('inf')
        # 枚举“最后一次合并”的分割点 k：
        # 先把 [l..k] 和 [k+1..r] 分别合并，每段的最小代价分别是 dp[l][k] 与 dp[k+1][r]
        for k in range(l, r):
            # 注意：此处仅累加“子区间内部合并”的最小代价，还未加上“最后把两堆合成一堆”的代价
            cost = dp[l][k] + dp[k + 1][r]
            if cost < best:
                best = cost
        # 最后一次把两堆合并的代价等于区间 [l..r] 的元素和（两堆相加）
        # 因此完整转移：dp[l][r] = min_k dp[l][k] + dp[k+1][r] + sum(l..r)
        dp[l][r] = best + range_sum(l, r)

return dp[0][n - 1]

if name == "main": arr = [6, 4, 4, 6] print(min_merge_cost(arr))