Ligh0x74's Blog

2023-10-26发表2024-09-02更新基础 / 模板10 分钟读完 (大约1539个字)

本文内容参考《算法》，《算法导论》，OI Wiki。

字符串匹配

例题

28. 找出字符串中第一个匹配项的下标。

暴力

时间复杂度：最坏 $O(NM)$，平均 $O(N)$。
空间复杂度：$O(1)$。

private static int bruteForce(String text, String pattern) {
    int i, j;
    int n = text.length(), m = pattern.length();
    for (i = 0, j = 0; i < n && j < m; i++) {
        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
        } else {
            i -= j;
            j = 0;
        }
    }
    return j == m ? i - m : -1;
}

KMP

时间复杂度：$O(N)$。
空间复杂度：$O(M)$。

private static int kmp(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    if (m > n) return -1;
    
    // 处理模式串
    // next[i] 表示 pattern 的子串 [0, i] 的最长相等前后缀的长度
    int[] next = new int[m];
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        next[i] = j;
    }
    
    // 匹配文本串
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}

Boyer-Moore

时间复杂度：最坏 $O(NM)$，平均 $O(\frac{N}{M})$。
空间复杂度：$O®$。

1	System.out.println("TODO");

Rabin-Karp

时间复杂度：$O(N)$。
空间复杂度：$O(1)$。

private static final int P = 13331;

// MOD = 2^64
private static int rabinKarp(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    if (m > n) return -1;

    long PM = pow(P, m - 1);
    long patHash = hash(pattern, m);
    long txtHash = hash(text, m);
    if (txtHash == patHash) {
        return 0;
    }

    for (int i = m; i < n; i++) {
        txtHash = txtHash - text.charAt(i - m) * PM;
        txtHash = txtHash * P + text.charAt(i);
        if (txtHash == patHash) {
            return i - m + 1;
        }
    }
    return -1;
}

private static long pow(int a, int n) {
    long res = 1L, x = a;
    for (; n != 0; x *= x, n >>= 1) {
        if ((n & 1) == 1) {
            res *= x;
        }
    }
    return res;
}

private static long hash(String s, int m) {
    long h = 0L;
    for (int i = 0; i < m; i++) {
        h = h * P + s.charAt(i);
    }
    return h;
}

字符串哈希

例题

E. Compress Words（这题使用 $MOD=2^{64}$ 一直在第 65 个测试点 WA，看来还是模质数比较好）。

实现

时间复杂度：预处理 $O(N)$，获取哈希值 $O(1)$。
空间复杂度：$O(N)$。

class StringHash {
    private final int K = 2;
    private static final long[] b = {131, 13331};
    private static final long[] m = {1_000_000_007, 998244353};

    private int index;
    private final long[][] h, p;

    public StringHash(int n) {
        h = new long[K][n + 1];
        p = new long[K][n + 1];
        for (int i = 0; i < K; i++) {
            p[i][0] = 1;
        }
    }

    public StringHash(char[] s) {
        this(s.length);
        for (char c : s) add(c);
    }

    public void add(char c) {
        for (int j = 0; j < K; j++) {
            p[j][index + 1] = p[j][index] * b[j] % m[j];
            h[j][index + 1] = (h[j][index] * b[j] + c) % m[j];
        }
        index++;
    }

    public long[] get(int l, int r) {
        long[] res = new long[K];
        for (int i = 0; i < K; i++) {
            long t = h[i][r + 1] - h[i][l] * p[i][r - l + 1];
            res[i] = (t % m[i] + m[i]) % m[i];
        }
        return res;
    }

    public int length() {
        return index;
    }
}

字典树（Trie）

例题

实现

时间复杂度：插入和查找都是 $O(k)$，其中 $k$ 为字符串的长度。
空间复杂度：$O(nR)$，其中 $n$ 为节点总数，$R$ 为字母表大小。

class Trie {
    private static final int R = 26;
    private final Node root;

    private static class Node {
        boolean exist;
        Node[] next = new Node[R];
    }

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.next[idx] == null) {
                node.next[idx] = new Node();
            }
            node = node.next[idx];
        }
        node.exist = true;
    }

    public boolean search(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.next[idx] == null) {
                return false;
            }
            node = node.next[idx];
        }
        return node.exist;
    }
}

AC 自动机

例题

P5357 【模板】AC 自动机（二次加强版）。

实现

时间复杂度：插入 $O(k)$，构建 $O(nR)$，查询 $O(k+n)$，其中 $k$ 为字符串的长度。
空间复杂度：$O(nR)$，其中 $n$ 为节点总数，$R$ 为字母表大小。

class AhoCorasickAutomaton {
    private static final int R = 26;
    private final Node root;

    // 按插入顺序存储模式串尾字符对应的节点
    private final List<Node> patternNodes;

    // 所有节点按层次遍历顺序存储（代码没有存根节点）
    private final List<Node> levelOrderNodes;

    private static class Node {
        int cnt; // 节点出现在文本串中的次数，懒更新
        Node fail; // 节点的失配指针，指向当前节点的最长后缀节点
        Node[] next = new Node[R];
    }

    public AhoCorasickAutomaton() {
        root = new Node();
        patternNodes = new ArrayList<>();
        levelOrderNodes = new ArrayList<>();
    }

    // 插入模式串
    public void insert(String pattern) {
        Node node = root;
        for (int i = 0; i < pattern.length(); i++) {
            int idx = pattern.charAt(i) - 'a';
            if (node.next[idx] == null) {
                node.next[idx] = new Node();
            }
            node = node.next[idx];
        }
        patternNodes.add(node);
    }

    // 构建失配指针和 Trie 图
    public void build() {
        // 将根节点的直接子节点入队，并构建节点的失配指针和 Trie 图
        // 提前入队是因为根节点和其直接子节点与其他节点的处理逻辑不同
        root.fail = root;
        Queue<Node> q = new LinkedList<>();
        for (int i = 0; i < R; i++) {
            if (root.next[i] == null) {
                root.next[i] = root;
            } else {
                root.next[i].fail = root;
                q.offer(root.next[i]);
            }
        }
        // 层次遍历，构建失配指针和 Trie 图
        while (!q.isEmpty()) {
            Node node = q.poll();
            levelOrderNodes.add(node);
            for (int i = 0; i < R; i++) {
                if (node.next[i] == null) {
                    node.next[i] = node.fail.next[i];
                } else {
                    node.next[i].fail = node.fail.next[i];
                    q.offer(node.next[i]);
                }
            }
        }
    }

    // 查询每个模式串在文本串中的出现次数
    public void query(String text, int[] cnt) {
        // 懒更新出现次数
        Node node = root;
        for (int i = 0; i < text.length(); i++) {
            int idx = text.charAt(i) - 'a';
            node = node.next[idx];
            node.cnt++;
        }
        // 倒序层次遍历，进一步沿着失配指针传递出现次数
        // 倒序遍历是因为失配指针必然在更上层，所以从下向上传递可以保证正确性
        for (int i = levelOrderNodes.size() - 1; i >= 0; i--) {
            node = levelOrderNodes.get(i);
            node.fail.cnt += node.cnt;
        }
        // 获取每个模式串的出现次数
        for (int i = 0; i < patternNodes.size(); i++) {
            cnt[i] += patternNodes.get(i).cnt;
        }
    }
}

正则表达式

例题

10. 正则表达式匹配。使用动态规划或者构造非确定有限状态自动机（NFA）。

实现

时间复杂度：构造 NFA $O(m)$，匹配 $O(nm)$，其中 $m$ 为正则表达式的长度，$n$ 为文本串的长度。
空间复杂度：构造 NFA $O(m)$，匹配 $O(m)$。

1	System.out.println("TODO");

2023-10-26发表2024-09-02更新基础 / 模板17 分钟读完 (大约2551个字)

排序算法

本文内容参考 sorting-algorithms，《算法》，《算法导论》。（~~强迫症，最后还是把描述性的文字删了，只贴代码~~）

验证算法的正确性，可以使用：912. 排序数组，148. 排序链表，164. 最大间距。

简单概述

理想的排序算法

稳定性：相同键不会重新排序。
原地排序：不使用额外空间存储排序数据。
最坏情况 $O(n\log{n})$ 次比较，$O(n)$ 次交换。
适应性：当数据接近排序或唯一键很少时，时间复杂度为 $O(n)$。

如何看待常数因子的改进方案

摘抄自《算法》的一段内容：在每一节中，我们会将书中的每个算法都看做某种应用的关键。但在整体上，我们希望学习的是为每种应用找到最合适的算法。我们并不是在推荐读者一定要实现所有提到的改进方法，而是提醒大家不要对算法初始实现的性能盖棺定论。研究一个新问题时，最好的方法是先实现一个你能想到的最简单的程序，当它成为瓶颈的时候再继续改进它。实现那些只能把运行时间缩短某个常数因子的改进措施可能并不值得。你需要用实验来检验一项改进，正如本书练习所演示的那样。

冒泡排序

稳定性：稳定。
时间复杂度：$O(n^{2})$。
空间复杂度：$O(1)$。
数据接近排序时，时间复杂度为 $O(n)$。

private static void bubbleSort(int[] nums) {
    int n = nums.length, pos;
    for (int i = n - 1; i > 0; i = pos) {
        pos = 0;
        for (int j = 0; j < i; j++) {
            // 稳定性的关键
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
                // 将最后交换的位置，作为下次冒泡的上界
                pos = j;
            }
        }
    }
}

选择排序

稳定性：不稳定。
时间复杂度：$O(n^{2})$。元素的交换次数最少的排序算法。
空间复杂度：$O(1)$。

private static void selectionSort(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) swap(nums, minIndex, i);
    }
}

插入排序

稳定性：稳定。
时间复杂度：$O(n^{2})$。元素的交换次数等于逆序数。
空间复杂度：$O(1)$。
数据接近排序时，时间复杂度为 $O(n)$。

private static void insertionSort(int[] nums) {
    int n = nums.length;
    for (int i = 1; i < n; i++) {
        int j = i - 1, t = nums[i];
        // 稳定性的关键
        for (; j >= 0 && nums[j] > t; j--) {
            nums[j + 1] = nums[j];
        }
        nums[j + 1] = t;
    }
}

希尔排序

稳定性：不稳定。
时间复杂度：使用 Knuth 增量序列 $O(n^{\frac{3}{2}})$，。Knuth 增量序列：$1,4,13,40,\dots,\frac{3^{k}-1}{2}$，相当于首项为 $1$，公比为 $3$ 的数列的前缀和。
空间复杂度：$O(1)$。
数据接近排序时，时间复杂度为 $O(n\log{n})$。

private static void insertionSort(int[] nums) {
    int n = nums.length, h = 1;
    while (h < n / 3) h = 3 * h + 1;
    while (h >= 1) {
        for (int i = h; i < n; i++) {
            int j = i - h, t = nums[i];
            for (; j >= 0 && nums[j] > t; j -= h) {
                nums[j + h] = nums[j];
            }
            nums[j + h] = t;
        }
        h /= 3;
    }
}

归并排序

稳定性：稳定的。
时间复杂度：$O(n\log{n})$。
空间复杂度：排序数组 $O(n)$；自顶向下排序链表 $O(\log{n})$（递归的空间），自底向上排序链表 $O(1)$。
顺序访问数据，缓存友好。

实现一：自顶向下（数组）

private static void mergeSort(int[] nums) {
    int n = nums.length;
    int[] aux = new int[n];
    mergeSort(nums, aux, 0, n - 1);
}

private static void mergeSort(int[] nums, int[] aux, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(nums, aux, lo, mid);
    mergeSort(nums, aux, mid + 1, hi);
    merge(nums, aux, lo, mid, hi);
}

private static void merge(int[] nums, int[] aux, int lo, int mid, int hi) {
    for (int i = lo; i <= hi; i++) {
        aux[i] = nums[i];
    }
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) nums[k] = aux[j++];
        else if (j > hi) nums[k] = aux[i++];
        // 稳定性的关键
        else if (aux[i] <= aux[j]) nums[k] = aux[i++];
        else nums[k] = aux[j++];
    }
}

实现二：自底向上（数组）

private static void mergeSort(int[] nums) {
    int n = nums.length;
    int[] aux = new int[n];
    for (int len = 1; len < n; len += len) {
        for (int i = 0; i + len < n; i += len << 1) {
            merge(nums, aux, i, i + len - 1, Math.min(n - 1, i + (len << 1) - 1));
        }
    }
}

private static void merge(int[] nums, int[] aux, int lo, int mid, int hi) {
    for (int i = lo; i <= hi; i++) {
        aux[i] = nums[i];
    }
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) nums[k] = aux[j++];
        else if (j > hi) nums[k] = aux[i++];
        // 稳定性的关键
        else if (aux[i] <= aux[j]) nums[k] = aux[i++];
        else nums[k] = aux[j++];
    }
}

实现三：自顶向下（链表）

private static ListNode mergeSort(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    // 分为两个子链表
    ListNode mid = middleNode(head);
    ListNode next = mid.next;
    mid.next = null;

    head = mergeSort(head);
    next = mergeSort(next);
    return merge(head, next);
}

// 返回合并链表的头节点
private static ListNode merge(ListNode head1, ListNode head2) {
    ListNode dummy = new ListNode(), curr = dummy;
    while (head1 != null && head2 != null) {
        // 稳定性的关键
        if (head1.val <= head2.val) {
            curr.next = head1;
            head1 = head1.next;
        } else {
            curr.next = head2;
            head2 = head2.next;
        }
        curr = curr.next;
    }
    curr.next = head1 != null ? head1 : head2;
    return dummy.next;
}

// 调用保证 head != null，并且如果有两个中间节点，则返回前一个（不然会无限递归）
// 使用 fast = head.next 可以保证返回前一个中间节点
// 使用 fast = head 可以保证返回后一个中间节点
private static ListNode middleNode(ListNode head) {
    if (head == null) return head;
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

实现四：自底向上（链表）

下面这个是没有提前计算链表长度，没有断开链表的解法。

private static ListNode mergeSort(ListNode head) {
    if (head == null || head.next == null) return head;

    int len = 1;
    ListNode dummy = new ListNode(-1, head);

    while (true) {
        // 两个子链表的头节点的前一个节点
        ListNode prev1, prev2;
        prev1 = prev2 = dummy;
        while (true) {
            for (int i = 0; i < len && prev2 != null; i++) {
                prev2 = prev2.next;
            }
            if (prev2 == null || prev2.next == null) break;

            prev1 = prev2 = merge(prev1, prev2, len);
        }
        // 如果该轮没有进行合并操作，则排序完成
        if (prev1 == dummy) break;
        len += len;
    }
    return dummy.next;
}

// 返回合并链表的尾节点
private static ListNode merge(ListNode prev1, ListNode prev2, int len) {
    // 判断条件：第一个链表未结束 && 第二个链表未结束（考虑长度不足的情况）
    while (prev1 != prev2 && len != 0 && prev2.next != null) {
        // 稳定性的关键
        if (prev1.next.val > prev2.next.val) {
            // 将 prev2.next 插入到 prev1 之后
            ListNode temp = prev2.next;
            prev2.next = prev2.next.next;
            temp.next = prev1.next;
            prev1.next = temp;
            len--;
        }
        prev1 = prev1.next;
    }
    // 使 prev2 指向合并链表的尾节点
    while (len-- != 0 && prev2.next != null) prev2 = prev2.next;
    return prev2;
}

快速排序

稳定性：不稳定。
时间复杂度：期望 $O(n\log{n})$。
空间复杂度：期望 $O(\log{n})$。
如果使用三路快排，数据包含大量重复元素时，时间复杂度为 $O(n)$。

实现一：二路快排

private static void quickSort(int[] nums) {
    int n = nums.length;
    quickSort(nums, 0, n - 1);
}

private static void quickSort(int[] nums, int lo, int hi) {
    if (lo >= hi) return;
    int index = partition(nums, lo, hi);
    quickSort(nums, lo, index - 1);
    quickSort(nums, index + 1, hi);
}

private static int partition(int[] nums, int lo, int hi) {
    // 三数取中
    int mid = median3(nums, lo, lo + (hi - lo) / 2, hi);
    swap(nums, lo, mid);
    
    int key = nums[lo];
    int i = lo, j = hi + 1;
    while (true) {
        // 和切分元素相等的元素也会停顿并交换
        while (nums[++i] < key && i != hi);
        while (nums[--j] > key);
        if (i >= j) break;
        swap(nums, i, j);
    }
    swap(nums, lo, j);
    return j;
}

实现二：三路快排

private static final Random RANDOM = new Random();

private static void quickSort(int[] nums) {
    int n = nums.length;
    quickSort(nums, 0, n - 1);
}

private static void quickSort(int[] nums, int lo, int hi) {
    if (lo >= hi) return;

    // 随机选择
    int randomIndex = lo + RANDOM.nextInt(hi - lo + 1);
    swap(nums, randomIndex, lo);

    int key = nums[lo];
    int lt = lo, gt = hi, i = lo + 1;
    while (i <= gt) {
        if (nums[i] < key) swap(nums, i++, lt++);
        else if (nums[i] > key) swap(nums, i, gt--);
        else i++;
    }

    quickSort(nums, lo, lt - 1);
    quickSort(nums, gt + 1, hi);
}

堆排序

稳定性：不稳定。
时间复杂度：$O(n\log{n})$。
空间复杂度：$O(1)$。
随机访问数据，缓存不友好。

public static void heapSort(int[] nums) {
    int n = nums.length;

    // 建堆 - 时间复杂度 O(n)
    for (int i = n / 2 - 1; i >= 0; i--) {
        sink(nums, i, n - 1);
    }

    // 排序 - 时间复杂度 O(nlog(n))
    for (int i = n - 1; i > 0; ) {
        swap(nums, 0, i--);
        sink(nums, 0, i);
    }
}

private static void sink(int[] nums, int i, int n) {
    int t = nums[i];
    while (2 * i + 1 <= n) {
        int j = 2 * i + 1;
        if (j + 1 <= n && nums[j + 1] > nums[j]) {
            j++;
        }
        if (t >= nums[j]) break;
        nums[i] = nums[j];
        i = j;
    }
    nums[i] = t;
}

计数排序

稳定性：稳定。
时间复杂度：$O(n+k)$。
空间复杂度：$O(n+k)$。

// 元素取值范围 [0,k)
private static int[] countingSort(int[] nums, int k) {
    int n = nums.length;
    int[] cnt = new int[k];
    int[] res = new int[n];

    // 计数
    for (int x : nums) {
        cnt[x]++;
    }

    // 前缀和
    for (int i = 1; i < k; i++) {
        cnt[i] += cnt[i - 1];
    }

    // 排序（倒序遍历，保证稳定性）
    for (int i = n - 1; i >= 0; i--) {
        res[--cnt[nums[i]]] = nums[i];
    }
    return res;
}

基数排序

稳定性：稳定。
时间复杂度：$O(d\cdot (n+k))$。
空间复杂度：$O(n+k)$。

// 元素最多有 d 位
private static int[] radixSort(int[] nums, int d) {
    int n = nums.length;
    int[] cnt = new int[10];
    int[] aux = new int[n];
    int divisor = 1;
    for (int i = 0; i < d; i++) {
        countingSort(nums, cnt, aux, divisor);
        
        Arrays.fill(cnt, 0);
        divisor *= 10;
        
        int[] t = nums;
        nums = aux;
        aux = t;
    }
    return nums;
}

private static void countingSort(int[] nums, int[] cnt, int[] aux, int divisor) {
    int n = nums.length;

    // 计数
    for (int x : nums) {
        cnt[x / divisor % 10]++;
    }

    // 前缀和
    for (int i = 1; i < 10; i++) {
        cnt[i] += cnt[i - 1];
    }

    // 排序（倒序遍历，保证稳定性）
    for (int i = n - 1; i >= 0; i--) {
        aux[--cnt[nums[i] / divisor % 10]] = nums[i];
    }
}

桶排序

稳定性：取决于桶内的排序策略。
时间复杂度：期望 $O(n)$。（输入数据均匀分布时）
空间复杂度：$O(n+m)$。

private static void bucketSort(int[] nums) {
    int n = nums.length;

    if (n <= 1) return;

    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int x : nums) {
        min = Math.min(min, x);
        max = Math.max(max, x);
    }

    // 小心除以零
    int inter = Math.max(1, (max - min) / (n - 1));
    int bucketSize = (max - min) / inter + 1;

    List<Integer>[] buckets = new List[bucketSize];
    Arrays.setAll(buckets, k -> new ArrayList<>());

    for (int x : nums) {
        int i = (x - min) / inter;
        buckets[i].add(x);

        // 插入排序
        int j = buckets[i].size() - 1;
        for (; j > 0 && buckets[i].get(j - 1) > x; j--) {
            buckets[i].set(j, buckets[i].get(j - 1));
        }
        buckets[i].set(j, x);
    }

    int idx = 0;
    for (var bucket : buckets) {
        for (int x : bucket) {
            nums[idx++] = x;
        }
    }
}

2023-10-26发表2024-09-02更新基础 / 模板8 分钟读完 (大约1252个字)

动态规划

本文内容参考《算法导论》，OI Wiki。

基础知识

动态规划方法通常用来求解最优化问题。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。

适合应用动态规划方法求解的最优化问题应该具备两个要素：最优子结构和重叠子问题。

最优子结构：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。
重叠子问题：如果问题的递归算法会反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质。

子问题图

子问题图是一个有向图，每个顶点唯一的对应一个子问题。若求子问题 $x$ 的最优解时需要直接用到子问题 $y$ 的最优解，那么在子问题图中就会有一条从子问题 $x$ 的顶点到子问题 $y$ 的顶点的有向边。

自顶向下动态规划处理子问题图中顶点的顺序为拓扑序，自底向上动态规划处理子问题图中顶点的顺序为逆拓扑序。

通常情况下，动态规划算法的运行时间与子问题图中顶点和边的数量呈线性关系。

选择自顶向下，还是自底向上

通常情况下，如果每个子问题都必须至少求解一次，自底向上动态规划算法会更快，因为没有递归调用的开销，而且对于某些问题，可以利用表的访问模式降低时空开销。如果子问题空间中的某些子问题完全不必求解，自顶向下动态规划算法会更快，因为它只会求解那些必要的子问题。

背包 DP

题目：有 $n$ 种物品和一个容量为 $W$ 的背包，每种物品有数量 $k_{i}$、重量 $w_{i}$ 和价值 $v_{i}$ 三种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

0-1 背包

每种物品只能取一次，即 $k_{i}=1$ 对任意 $i$ 都成立。

转移方程：

$$ dp[i][j]=\max{(dp[i-1][j],dp[i-1][j-w[i]]+v[i])} $$

空间优化（倒序枚举）：

$$ dp[j]=\max{(dp[j],dp[j-w[i]]+v[i])} $$

完全背包

每种物品可以取无限次，即 $k_{i}=\infty$ 对任意 $i$ 都成立。

转移方程：

$$ dp[i][j]=\max_{k=0}^{\infty}{dp[i-1][j-k\cdot w[i]]+k\cdot v[i]} $$

方程优化：

$$ dp[i][j]=\max{(dp[i-1][j],dp[i][j-w[i]]+v[i])} $$

空间优化（正序枚举）：

$$ dp[j]=\max(dp[j],dp[j-w[i]]+v[i]) $$

多重背包

每种物品可以取 $k_{i}$ 次，即 $k_{i}\in\mathbb{N}$ 对任意 $i$ 都成立。

转移方程：

$$ dp[i][j]=\max_{k=0}^{k[i]}{dp[i-1][j-k\cdot w[i]]+k\cdot v[i]} $$

二进制分组优化：将每种物品的 $k_{i}$ 拆分为多个组，每组的数量为 $2^{0},2^{1},\dots,2^{\lfloor{\log{k_{i}+1}}\rfloor -1}$，如果 $k_{i}+1$ 不是二的幂，就将多余的数量作为一组，最后将 $k_{i}$ 拆出来的每组都看作数量为 $1$ 的新物品，从而转化为 0-1 背包。可以证明，如果选择 $x$ 次第 $i$ 种物品，其中 $x\in[0,k_{i}]$，则该选择方式总是可以由分组后的新物品的某个组合表示。

例题

线性 DP：1143. 最长公共子序列，300. 最长递增子序列，72. 编辑距离。
背包 DP：416. 分割等和子集，322. 零钱兑换，2902. 和带限制的子多重集合的数目。
区间 DP：516. 最长回文子序列，1000. 合并石头的最低成本。
树形 DP：2646. 最小化旅行的价格总和，834. 树中距离之和，2867. 统计树中的合法路径数目。
状压 DP：526. 优美的排列，Mondriaan’s Dream。
数位 DP：233. 数字 1 的个数，1012. 至少有 1 位重复的数字。
概率 DP：D. Bag of mice，E - Roulettes。

字符串匹配

例题

暴力

KMP

Boyer-Moore

Rabin-Karp

字符串哈希

例题

实现

字典树（Trie）

例题

实现

AC 自动机

例题

实现

正则表达式

例题

实现

简单概述

冒泡排序

选择排序

插入排序

希尔排序

归并排序

快速排序

堆排序

计数排序

基数排序

桶排序

基础知识

背包 DP

例题

链接

分类

最新文章

归档

标签

链接