动态规划篇——线性DP
动态规划篇——线性DP
本次我们介绍动态规划篇的线性DP，我们会从下面几个角度来介绍：
- 数字三角形
- 最长上升子序列I
- 最长上升子序列II
- 最长公共子序列
- 最短编辑距离
数字三角形
我们首先介绍一下题目：
/*题目概述*/
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层
要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
/*具体需求*/
// 输入格式
第一行包含整数 n，表示数字三角形的层数。
接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。
// 输出格式
输出一个整数，表示最大的路径数字和。
// 数据范围
1 ≤ n ≤ 500
−10000 ≤ 三角形中的整数 ≤ 10000
// 输入样例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
// 输出样例：
30
然后我们进行分析：
/*题目分析*/
我们采用DP思想
首先我们采用a[i][j]来表示第i行，第j列的数字；我们采用f[i][j]表示到达第i行第j列的路径最大值
那么我们的f[i][j]就有两条来源，分别来自于f[i][j]的左上和右上，也就是f[i-1][j-1]和f[i-1][j]
那么我们的当前值f[i][j]的最大值也就是左上和右上的最大值加上当前a[i][j]即可，注意每一行都是最大值，所以前面f[i][j]也是最大值
注意：由于上面操作涉及到j-1和j，可能会涉及边界问题，为了减少if判断条件，我们的操作从下标为1开始！
我们给出具体代码：
import java.util.Scanner;
public class NumberTriangle {
final static int N =100010;
final static int INF = Integer.MIN_VALUE/2;
// 提前设置信息,a为当前值，f为路径max
static int n;
static int[][] a = new int[N][N];
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
// a赋值
for (int i = 1; i 最长上升子序列I
我们首先介绍一下题目：
/*题目概述*/
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
/*具体需求*/
// 输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
// 输出格式
输出一个整数，表示最大长度。
// 数据范围
1 ≤ N ≤ 1000，
−109 ≤ 数列中的数 ≤ 109
// 输入样例：
7
3 1 2 1 8 5 6
// 输出样例：
4
然后我们进行分析：
/*题目分析*/
我们采用DP思想
我们采用a[i]表示第i个数的值，我们采用f[i]表示以当前值结尾的最长子序列长度
那么我们就需要采用双重循环，第一层循环用来遍历i，更新f[i]；第二层循环用来查找i之前的j，判断j我们给出具体代码：
import java.util.Scanner;
public class Main {
final static int N = 1010;
static int n;
static int[] a = new int[N];
static int[] f = new int[N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
// 赋值
for (int i = 1; i 最长上升子序列II
我们这里对最长上升子序列进行一个优化处理:
/*优化思路*/
我们在之前是与所有小于该点的数进行一一比较，也就是双循环
我们可以采用q数组来存放不同子序列长度下的最小值来作为判定条件，同时我们采用二分查找来优化查找时间复杂度
/*代码展示*/
import java.util.Scanner;
public class Main {
final static int N = 100010;
// a存放当前数组，q存放每种长度的最长上升子序列中结尾的最小值
static int n;
static int[] a = new int[N];
static int[] q = new int[N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
for (int i = 0; i > 1;
if(q[mid] 最长公共子序列
我们首先介绍一下题目：
/*题目概述*/
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
/*具体需求*/
// 输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。
// 输出格式
输出一个整数，表示最大长度。
// 数据范围
1 ≤ N, M ≤ 1000
// 输入样例：
4 5
acbd
abedc
// 输出样例：
3
然后我们进行分析：
/*题目分析*/
我们采用DP思想
我们使用f[i][j]来表示a字符串前i个字符和b字符串前j个字符之间的最大子序列长度
那么我们希望用之前的f来更新最新的f，我们主要分为四种状态；
f[i][j] = f[i-1][j-1]
f[i][j] = f[i-1][j]
f[i][j] = f[i][j-1]
f[i][j] = f[i-1][j-1]+1
我们需要注意的是：
f[i-1][j]和f[i][j-1]已经涵括了f[i-1][j-1]，所以我们可以少写一种情况
f[i][j] = f[i-1][j-1]+1情况只有当a[i]==b[i]时才会触发
我们给出具体代码：
import java.util.Scanner;
public class Main {
final static int N = 1010;
static int n,m;
static char[] a = new char[N];
static char[] b = new char[N];
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 赋值
n = scanner.nextInt();
m = scanner.nextInt();
String A = scanner.next();
for (int i = 1; i 最短编辑距离
我们首先介绍一下题目：
/*题目概述*/
给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：
删除–将字符串 A 中的某个字符删除。
插入–在字符串 A 的某个位置插入某个字符。
替换–将字符串 A 中的某个字符替换为另一个字符。
现在请你求出，将 A 变为 B 至少需要进行多少次操作。
/*具体需求*/
// 输入格式
第一行包含整数 n，表示字符串 A 的长度。
第二行包含一个长度为 n 的字符串 A。
第三行包含整数 m，表示字符串 B 的长度。
第四行包含一个长度为 m 的字符串 B。
字符串中均只包含大小写字母。
// 输出格式
输出一个整数，表示最少操作次数。
// 数据范围
1 ≤ n,m ≤ 1000
// 输入样例：
10
AGTCTGACGC
11
AGTAAGTAGGC
// 输出样例：
4
然后我们进行分析：
/*题目分析*/
我们采用DP思想
这里的DP思想其实和最长公共子序列很相似
我们使用f[i][j]来表示a字符串前i个字符和b字符串前j个字符之间进行匹配的最小操作数
我们需要提前设置一下初始值：
f[i][0]表示a的前i个字符和b为空时，这时我们需要对a进行i次减法：f[i][0] = i;
f[0][j]表示a为空和b的前j个字符时，这时我们需要对a进行i次加法：f[0][j] = i;
那么我们希望用之前的f来更新最新的f，我们主要分为两种状态；
当i和j变更时，我们需要对a做添加或删除：f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
当i和j同时变更，且a[i]==b[j],这时不需要操作：(a[i] == b[j]) f[i][j] = Math.min(f[i][j],f[i - 1][j - 1]);
但是如果不相等，我们需要进行修改操作：else f[i][j] = Math.min(f[i][j],f[i - 1][j - 1] + 1);
我们给出具体代码：
import java.util.*;
public class UpdateShort{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int N = 1010;
char[] a = new char[N];
char[] b = new char[N];
int[][] f = new int[N][N];
int n = scannernextInt();
String A = scanner.next();
int m = scanner.nextInt();
String B = scanner.next();
for(int i = 1 ; i 结束语
好的，关于动态规划篇的线性DP就介绍到这里，希望能为你带来帮助~
文章来源于互联网：动态规划篇——线性DP
THE END
二维码