DP笔记(2)：线性DP概念与例题集合

线性动态规划简介

线性动态规划：具有「线性」阶段划分的动态规划方法统称为线性动态规划（简称为「线性 DP」），如下图所示。

如果状态包含多个维度，但是每个维度上都是线性划分的阶段，也属于线性 DP。比如背包问题、区间 DP、数位 DP 等都属于线性 DP。

线性 DP 问题的划分方法有多种方式。

• 如果按照「状态的维度数」进行分类，我们可以将线性 DP 问题分为：

• 一维线性 DP 问题

• 二维线性 DP 问题

• 多维线性 DP 问题

• 如果按照「问题的输入格式」进行分类，我们可以将线性 DP 问题分为：

• 单串线性 DP 问题

• 双串线性 DP 问题

• 矩阵线性 DP 问题

• 无串线性 DP 问题

按照状态的维度数来分类，确实非常好辨认。本文中，我们将按照问题的输入格式进行分类，对线性 DP 问题中各种类型问题进行一一讲解。

单串线性 DP 问题

单串线性 DP 问题：问题的输入为单个数组或单个字符串的线性 DP 问题。状态一般可定义为dp[i]，表示为：

1. 「以数组中第i 个位置元素 nums[i] 为结尾的子数组（nums[0]...nums[i]）」的相关解。

2. 「以数组中第 i−1 个位置元素nums[i−1] 为结尾的子数组（nums[0]...nums[i−1]）」的相关解。

3. 「以数组中前 i 个元素为子数组（nums[0]...nums[i−1]）」的相关解。

这 3种状态的定义区别在于相差一个元素nums[i]。

1. 第 1 种状态：子数组的长度为 i+1，子数组长度不可为空；

2. 第 2种状态、第 3 种状态：这两种状态描述是相同的。子数组的长度为i，子数组长度可为空。在i=0 时，方便用于表示空数组（以数组中前 0 个元素为子数组）。

双串线性 DP 问题

双串线性 DP 问题：问题的输入为两个数组或两个字符串的线性 DP 问题。状态一般可定义为dp[i][j]，表示为：

1. 「以第一个数组中第i 个位置元素 nums1[i] 为结尾的子数组（nums1[0]...nums1[i]）」与「以第二个数组中第 j 个位置元素 nums2[j] 为结尾的子数组（nums2[0]...nums2[j]）」的相关解。

2. 「以第一个数组中第 i−1 个位置元素 nums1[i−1] 为结尾的子数组（nums1[0]...nums1[i−1]）」与「以第二个数组中第 j−1 个位置元素 nums2[j−1] 为结尾的子数组（nums2[0]...nums2[j−1]）」的相关解。

3. 「以第一个数组中前 i 个元素为子数组（nums1[0]...nums1[i−1]）」与「以第二个数组中前 j 个元素为子数组（nums2[0]...nums2[j−1]）」的相关解。

这 33 种状态的定义区别在于相差一个元素 nums1[i] 或 nums2[j]。

1. 第 11 种状态：子数组的长度为 i+1 或 j+1，子数组长度不可为空

2. 第 22 种状态、第 33 种状态：子数组的长度为 i 或 j，子数组长度可为空。i=0 或j=0 时，方便用于表示空数组（以数组中前 00 个元素为子数组）。

矩阵线性 DP问题

矩阵线性 DP 问题：问题的输入为二维矩阵的线性 DP 问题。状态一般可定义为 dp[i][j]，表示为：从「位置 (0,0)(0,0)」到达「位置 (i,j)」的相关解。

无串线性 DP 问题

无串线性 DP 问题：问题的输入不是显式的数组或字符串，但依然可分解为若干子问题的线性 DP 问题。

线性 DP 题目

单串线性 DP 问题

双串线性 DP 问题

矩阵线性 DP 问题

无串线性 DP 问题

转载本站文章《DP笔记(2)：线性DP概念与例题集合》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9111.html