Java動(dòng)態(tài)規(guī)劃篇之線性DP的示例詳解
本次我們介紹動(dòng)態(tài)規(guī)劃篇的線性DP，我們會(huì)從下面幾個(gè)角度來(lái)介紹：
- 數(shù)字三角形
- 最長(zhǎng)上升子序列I
- 最長(zhǎng)上升子序列II
- 最長(zhǎng)公共子序列
- 最短編輯距離
數(shù)字三角形
我們首先介紹一下題目：
題目概述
給定一個(gè)如下圖所示的數(shù)字三角形，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇移動(dòng)至其左下方的結(jié)點(diǎn)或移動(dòng)至其右下方的結(jié)點(diǎn)，一直走到底層，要求找出一條路徑，使路徑上的數(shù)字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
具體需求
輸入格式
第一行包含整數(shù) n，表示數(shù)字三角形的層數(shù)。
接下來(lái) n 行，每行包含若干整數(shù)，其中第 i 行表示數(shù)字三角形第 i 層包含的整數(shù)。
輸出格式
輸出一個(gè)整數(shù)，表示最大的路徑數(shù)字和。
數(shù)據(jù)范圍
1 ≤ n ≤ 500
−10000 ≤ 三角形中的整數(shù) ≤ 10000
輸入樣例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
輸出樣例：
30
然后我們進(jìn)行分析：
題目分析
我們采用DP思想
首先我們采用a[i][j]來(lái)表示第i行，第j列的數(shù)字；我們采用f[i][j]表示到達(dá)第i行第j列的路徑最大值
那么我們的f[i][j]就有兩條來(lái)源，分別來(lái)自于f[i][j]的左上和右上，也就是f[i-1][j-1]和f[i-1][j]
那么我們的當(dāng)前值f[i][j]的最大值也就是左上和右上的最大值加上當(dāng)前a[i][j]即可，注意每一行都是最大值，所以前面f[i][j]也是最大值
注意：由于上面操作涉及到j(luò)-1和j，可能會(huì)涉及邊界問(wèn)題，為了減少if判斷條件，我們的操作從下標(biāo)為1開(kāi)始！
我們給出具體代碼：
import java.util.Scanner;
public class NumberTriangle {
final static int N =100010;
final static int INF = Integer.MIN_VALUE/2;
// 提前設(shè)置信息,a為當(dāng)前值，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 <= n; i++) {
for (int j = 1; j <= i; j++) {
a[i][j] = scanner.nextInt();
}
}
// f初始值(注意，這里的初始值需要聯(lián)通邊界也設(shè)置好初始值)
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= i+1; j++) {
f[i][j] = INF;
}
}
// 開(kāi)始DP
f[1][1] = a[1][1];
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
f[i][j] = Math.max(f[i-1][j-1],f[i-1][j]) + a[i][j];
}
}
// 提供返回值即可
int res = INF;
for (int i = 1; i <= n; i++) {
res = Math.max(res,f[n][i]);
}
System.out.println(res);
}
}
最長(zhǎng)上升子序列I
我們首先介紹一下題目：
題目概述
給定一個(gè)長(zhǎng)度為 N 的數(shù)列，求數(shù)值嚴(yán)格單調(diào)遞增的子序列的長(zhǎng)度最長(zhǎng)是多少。
具體需求
輸入格式
第一行包含整數(shù) N。
第二行包含 N 個(gè)整數(shù)，表示完整序列。
輸出格式
輸出一個(gè)整數(shù)，表示最大長(zhǎng)度。
數(shù)據(jù)范圍
1 ≤ N ≤ 1000，
−109 ≤ 數(shù)列中的數(shù) ≤ 109
輸入樣例
7
3 1 2 1 8 5 6
輸出樣例
4
然后我們進(jìn)行分析：
題目分析
我們采用DP思想
我們采用a[i]表示第i個(gè)數(shù)的值，我們采用f[i]表示以當(dāng)前值結(jié)尾的最長(zhǎng)子序列長(zhǎng)度
那么我們就需要采用雙重循環(huán)，第一層循環(huán)用來(lái)遍歷i，更新f[i]；第二層循環(huán)用來(lái)查找i之前的j，判斷j<i，則進(jìn)行f[i]更新
我們給出具體代碼：
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 <= n; i++) {
a[i] = scanner.nextInt();
}
// 開(kāi)始DP
for (int i = 1; i <= n; i++) {
// 最開(kāi)始只有他自己，默認(rèn)為1
f[i] = 1;
// 二重循環(huán)，更新fi
for (int j = 1; j < i; j++) {
if (a[j] < a[i]) f[i] = Math.max(f[i],f[j] + 1);
}
}
// 最后輸出結(jié)果即可
int res = 0;
for (int i = 1; i <= n; i++) {
res = Math.max(res,f[i]);
}
System.out.println(res);
}
}
最長(zhǎng)上升子序列II
我們這里對(duì)最長(zhǎng)上升子序列進(jìn)行一個(gè)優(yōu)化處理:
/*優(yōu)化思路*/
//我們?cè)谥笆桥c所有小于該點(diǎn)的數(shù)進(jìn)行一一比較，也就是雙循環(huán)
//我們可以采用q數(shù)組來(lái)存放不同子序列長(zhǎng)度下的最小值來(lái)作為判定條件，同時(shí)我們采用二分查找來(lái)優(yōu)化查找時(shí)間復(fù)雜度
/*代碼展示*/
import java.util.Scanner;
public class Main {
final static int N = 100010;
// a存放當(dāng)前數(shù)組，q存放每種長(zhǎng)度的最長(zhǎng)上升子序列中結(jié)尾的最小值
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 < n; i++) {
a[i] = scanner.nextInt();
}
// 我們首先需要設(shè)置q的前置條件，我們將長(zhǎng)度設(shè)置0，將q[0]設(shè)置為負(fù)無(wú)窮以便于a的值可以存放進(jìn)q中
int len = 0;
q[0] = -(int)-2e9;
// 一個(gè)數(shù)可以接在什么位置，用二分來(lái)尋找每種長(zhǎng)度的結(jié)尾的最小值比這個(gè)數(shù)小的的位置，然后長(zhǎng)度加1，
// 就是新的最長(zhǎng)上升子序列的長(zhǎng)度
for(int i = 0 ; i < n ; i ++ ){
int l = 0,r = len;
while(l < r){
int mid = l + r + 1 >> 1;
if(q[mid] < a[i]) l = mid;
else r = mid - 1;
}
// 找到位置之后更新長(zhǎng)度
len = Math.max(len, r + 1);
// 比如因?yàn)檎业降臄?shù)q[4]是小于的a最大的數(shù)，所以后面的一個(gè)數(shù)q[5]就是大于等于這個(gè)數(shù)
// 然后我們可以接在q[4]后面，所以現(xiàn)在長(zhǎng)度是5，變成q[5],然后因?yàn)槲覀兊倪@個(gè)數(shù)是小于或者等于q[5]
// 所以直接將值賦上就行
q[r + 1] = a[i];
}
System.out.println(len);
}
}
最長(zhǎng)公共子序列
我們首先介紹一下題目：
題目概述
給定兩個(gè)長(zhǎng)度分別為 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串長(zhǎng)度最長(zhǎng)是多少。
具體需求
輸入格式
第一行包含兩個(gè)整數(shù) N 和 M。
第二行包含一個(gè)長(zhǎng)度為 N 的字符串，表示字符串 A。
第三行包含一個(gè)長(zhǎng)度為 M 的字符串，表示字符串 B。
字符串均由小寫(xiě)字母構(gòu)成。
輸出格式
輸出一個(gè)整數(shù)，表示最大長(zhǎng)度。
數(shù)據(jù)范圍
1 ≤ N, M ≤ 1000
輸入樣例
4 5
acbd
abedc
輸出樣例
3
然后我們進(jìn)行分析：
題目分析
我們采用DP思想
我們使用f[i][j]來(lái)表示a字符串前i個(gè)字符和b字符串前j個(gè)字符之間的最大子序列長(zhǎng)度
那么我們希望用之前的f來(lái)更新最新的f，我們主要分為四種狀態(tài)；
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]已經(jīng)涵括了f[i-1][j-1]，所以我們可以少寫(xiě)一種情況
f[i][j] = f[i-1][j-1]+1情況只有當(dāng)a[i]==b[i]時(shí)才會(huì)觸發(fā)
我們給出具體代碼：
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 <= n; i++) {
a[i] = A.charAt(i-1);
}
String B = scanner.next();
for (int i = 1; i <= m; i++) {
b[i] = B.charAt(i-1);
}
// DP算法
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 第一種情況：f[i-1][j]和f[i][j-1]
f[i][j] = Math.max(f[i-1][j],f[i][j-1]);
// 第二種情況：f[i-1][j-1] + 1
if (a[i] == b[j]) f[i][j] = Math.max(f[i-1][j-1]+1,f[i][j]);
}
}
// 輸出
System.out.println(f[n][m]);
}
}
最短編輯距離
我們首先介紹一下題目：
題目概述
給定兩個(gè)字符串 A 和 B，現(xiàn)在要將 A 經(jīng)過(guò)若干操作變?yōu)?B，可進(jìn)行的操作有：
刪除–將字符串 A 中的某個(gè)字符刪除。
插入–在字符串 A 的某個(gè)位置插入某個(gè)字符。
替換–將字符串 A 中的某個(gè)字符替換為另一個(gè)字符。
現(xiàn)在請(qǐng)你求出，將 A 變?yōu)?B 至少需要進(jìn)行多少次操作。
具體需求
輸入格式
第一行包含整數(shù) n，表示字符串 A 的長(zhǎng)度。
第二行包含一個(gè)長(zhǎng)度為 n 的字符串 A。
第三行包含整數(shù) m，表示字符串 B 的長(zhǎng)度。
第四行包含一個(gè)長(zhǎng)度為 m 的字符串 B。
字符串中均只包含大小寫(xiě)字母。
輸出格式
輸出一個(gè)整數(shù)，表示最少操作次數(shù)。
數(shù)據(jù)范圍
1 ≤ n,m ≤ 1000
輸入樣例
10
AGTCTGACGC
11
AGTAAGTAGGC
輸出樣例
4
然后我們進(jìn)行分析：
題目分析
我們采用DP思想
這里的DP思想其實(shí)和最長(zhǎng)公共子序列很相似
我們使用f[i][j]來(lái)表示a字符串前i個(gè)字符和b字符串前j個(gè)字符之間進(jìn)行匹配的最小操作數(shù)
我們需要提前設(shè)置一下初始值：
- f[i][0]表示a的前i個(gè)字符和b為空時(shí)，這時(shí)我們需要對(duì)a進(jìn)行i次減法：f[i][0] = i;
- f[0][j]表示a為空和b的前j個(gè)字符時(shí)，這時(shí)我們需要對(duì)a進(jìn)行i次加法：f[0][j] = i;
那么我們希望用之前的f來(lái)更新最新的f，我們主要分為兩種狀態(tài)；
當(dāng)i和j變更時(shí)，我們需要對(duì)a做添加或刪除：f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
當(dāng)i和j同時(shí)變更，且a[i]==b[j],這時(shí)不需要操作：(a[i] == b[j]) f[i][j] = Math.min(f[i][j],f[i - 1][j - 1]);
但是如果不相等，我們需要進(jìn)行修改操作：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 <= n ; i ++ ) {
a[i] = A.charAt(i - 1);
f[i][0] = i; // 處理邊界,字符串b是0,a進(jìn)行n次刪除
}
for(int i = 1 ; i <= m ; i ++ ){
b[i] = B.charAt(i - 1);
f[0][i] = i; // 處理邊界,字符串a(chǎn)是0,a進(jìn)行m次增加
}
for(int i = 1 ; i <= n ; i ++ ){
for(int j = 1 ; j <= m ; j ++ ){
// 刪除和增加操作
f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
// 最后一個(gè)數(shù)相同，不用進(jìn)行修改操作，則不用加1
if(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); // 修改操作
}
}
System.out.println(f[n][m]);
}
}到此這篇關(guān)于Java動(dòng)態(tài)規(guī)劃篇之線性DP的示例詳解的文章就介紹到這了,更多相關(guān)Java線性DP內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本文主要介紹了SpringBoot構(gòu)建ORM框架的方法步驟，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-02-02
IDEA實(shí)現(xiàn)遠(yuǎn)程調(diào)試步驟詳解
這篇文章主要介紹了IDEA實(shí)現(xiàn)遠(yuǎn)程調(diào)試步驟詳解，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
SSH框架實(shí)現(xiàn)表單上傳圖片實(shí)例代碼
本篇文章主要介紹了SSH框架實(shí)現(xiàn)表單上傳圖片實(shí)例代碼，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-09-09
IDEA maven引入SSL證書(shū)校驗(yàn)問(wèn)題及處理
這篇文章主要討論了在Maven項(xiàng)目中遇到依賴導(dǎo)入問(wèn)題,特別是關(guān)于PKIX路徑構(gòu)建失敗的錯(cuò)誤,文章提供了三種解決方法：手動(dòng)下載依賴、忽略SSL證書(shū)校驗(yàn)以及生成并導(dǎo)入SSL證書(shū),每種方法都有詳細(xì)的步驟和示例代碼,幫助開(kāi)發(fā)者解決這個(gè)問(wèn)題2025-02-02
這篇文章主要介紹了詳解Java中的hashcode,文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)java的小伙伴們有非常好的幫助,需要的朋友可以參考下2021-05-05
Java封裝實(shí)現(xiàn)自適應(yīng)的單位轉(zhuǎn)換工具類
這篇文章主要為大家詳細(xì)介紹了如何使用Java封裝實(shí)現(xiàn)一個(gè)自適應(yīng)的單位轉(zhuǎn)換工具類,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2025-03-03
本篇文章主要介紹了Java讀取TXT文件內(nèi)容的方法，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-06-06
SpringBoot XSS攻擊的常見(jiàn)形式與防范方法
XSS攻擊是指攻擊者在Web頁(yè)面的輸入數(shù)據(jù)中插入惡意腳本,當(dāng)其他用戶瀏覽該頁(yè)面時(shí),這些腳本就會(huì)在用戶的瀏覽器上執(zhí)行,可能導(dǎo)致信息泄露、會(huì)話劫持、惡意操作等安全風(fēng)險(xiǎn),本文給大家介紹了SpringBoot XSS攻擊的常見(jiàn)形式與防范方法,需要的朋友可以參考下2024-11-11
java大話之創(chuàng)建型設(shè)計(jì)模式教程示例
這篇文章主要為大家介紹了java大話之創(chuàng)建型設(shè)計(jì)模式教程示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-02-02
SpringAop @Aspect織入不生效,不執(zhí)行前置增強(qiáng)織入@Before方式
這篇文章主要介紹了SpringAop @Aspect織入不生效,不執(zhí)行前置增強(qiáng)織入@Before方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-12-12