快捷導(dǎo)航

Java動態(tài)規(guī)劃篇之線性DP的示例詳解

更新時間：2022年11月24日 08:16:28 作者：秋落雨微涼

這篇文章主要通過幾個例題為大家詳細(xì)介紹一些Java動態(tài)規(guī)劃中的線性DP，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)Java有一定的幫助，需要的可以參考一下

數(shù)字三角形

我們首先介紹一下題目：

題目概述

給定一個如下圖所示的數(shù)字三角形，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇移動至其左下方的結(jié)點(diǎn)或移動至其右下方的結(jié)點(diǎn)，一直走到底層，要求找出一條路徑，使路徑上的數(shù)字的和最大。

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

具體需求

輸入格式

第一行包含整數(shù) n，表示數(shù)字三角形的層數(shù)。

接下來 n 行，每行包含若干整數(shù)，其中第 i 行表示數(shù)字三角形第 i 層包含的整數(shù)。

輸出格式

輸出一個整數(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]來表示第i行，第j列的數(shù)字；我們采用f[i][j]表示到達(dá)第i行第j列的路徑最大值

那么我們的f[i][j]就有兩條來源，分別來自于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，可能會涉及邊界問題，為了減少if判斷條件，我們的操作從下標(biāo)為1開始！

我們給出具體代碼：

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;
            }
        }

        // 開始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);
    }
}

最長上升子序列I

我們首先介紹一下題目：

題目概述

給定一個長度為 N 的數(shù)列，求數(shù)值嚴(yán)格單調(diào)遞增的子序列的長度最長是多少。

具體需求

輸入格式

第一行包含整數(shù) N。

第二行包含 N 個整數(shù)，表示完整序列。

輸出格式

輸出一個整數(shù)，表示最大長度。

數(shù)據(jù)范圍

1 ≤ N ≤ 1000，

−109 ≤ 數(shù)列中的數(shù) ≤ 109

輸入樣例

7
3 1 2 1 8 5 6

輸出樣例

4

然后我們進(jìn)行分析：

題目分析

我們采用DP思想

我們采用a[i]表示第i個數(shù)的值，我們采用f[i]表示以當(dāng)前值結(jié)尾的最長子序列長度

那么我們就需要采用雙重循環(huán)，第一層循環(huán)用來遍歷i，更新f[i]；第二層循環(huán)用來查找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();
        }

        // 開始DP
        for (int i = 1; i <= n; 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);
    }
}

最長上升子序列II

我們這里對最長上升子序列進(jìn)行一個優(yōu)化處理:

/*優(yōu)化思路*/

//我們在之前是與所有小于該點(diǎn)的數(shù)進(jìn)行一一比較，也就是雙循環(huán)
    
//我們可以采用q數(shù)組來存放不同子序列長度下的最小值來作為判定條件，同時我們采用二分查找來優(yōu)化查找時間復(fù)雜度
    
/*代碼展示*/
    
import java.util.Scanner;

public class Main {

    final static int N = 100010;

    // a存放當(dāng)前數(shù)組，q存放每種長度的最長上升子序列中結(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的前置條件，我們將長度設(shè)置0，將q[0]設(shè)置為負(fù)無窮以便于a的值可以存放進(jìn)q中
        int len = 0;
        q[0] = -(int)-2e9;

        // 一個數(shù)可以接在什么位置，用二分來尋找每種長度的結(jié)尾的最小值比這個數(shù)小的的位置，然后長度加1，
        // 就是新的最長上升子序列的長度
        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;
            }
            // 找到位置之后更新長度
            len = Math.max(len, r + 1);

            // 比如因為找到的數(shù)q[4]是小于的a最大的數(shù)，所以后面的一個數(shù)q[5]就是大于等于這個數(shù)
            // 然后我們可以接在q[4]后面，所以現(xiàn)在長度是5，變成q[5],然后因為我們的這個數(shù)是小于或者等于q[5]
            // 所以直接將值賦上就行
            q[r + 1] = a[i];
        }

        System.out.println(len);
    }
}

最長公共子序列

我們首先介紹一下題目：

題目概述

給定兩個長度分別為 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串長度最長是多少。

具體需求

輸入格式

第一行包含兩個整數(shù) N 和 M。

第二行包含一個長度為 N 的字符串，表示字符串 A。

第三行包含一個長度為 M 的字符串，表示字符串 B。

字符串均由小寫字母構(gòu)成。

輸出格式

輸出一個整數(shù)，表示最大長度。

數(shù)據(jù)范圍

1 ≤ N, M ≤ 1000

輸入樣例

4 5
acbd
abedc

輸出樣例

3

然后我們進(jìn)行分析：

題目分析

我們采用DP思想

我們使用f[i][j]來表示a字符串前i個字符和b字符串前j個字符之間的最大子序列長度

那么我們希望用之前的f來更新最新的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]，所以我們可以少寫一種情況

f[i][j] = f[i-1][j-1]+1情況只有當(dāng)a[i]==b[i]時才會觸發(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]);

    }
}

最短編輯距離

我們首先介紹一下題目：

題目概述

給定兩個字符串 A 和 B，現(xiàn)在要將 A 經(jīng)過若干操作變?yōu)?B，可進(jìn)行的操作有：

刪除–將字符串 A 中的某個字符刪除。

插入–在字符串 A 的某個位置插入某個字符。

替換–將字符串 A 中的某個字符替換為另一個字符。

現(xiàn)在請你求出，將 A 變?yōu)?B 至少需要進(jìn)行多少次操作。

具體需求

輸入格式

第一行包含整數(shù) n，表示字符串 A 的長度。

第二行包含一個長度為 n 的字符串 A。

第三行包含整數(shù) m，表示字符串 B 的長度。

第四行包含一個長度為 m 的字符串 B。

字符串中均只包含大小寫字母。

輸出格式

輸出一個整數(shù)，表示最少操作次數(shù)。

數(shù)據(jù)范圍

1 ≤ n,m ≤ 1000

輸入樣例

10
AGTCTGACGC
11
AGTAAGTAGGC

輸出樣例

4

然后我們進(jìn)行分析：

題目分析

我們采用DP思想

這里的DP思想其實(shí)和最長公共子序列很相似

我們使用f[i][j]來表示a字符串前i個字符和b字符串前j個字符之間進(jìn)行匹配的最小操作數(shù)

我們需要提前設(shè)置一下初始值：

f[i][0]表示a的前i個字符和b為空時，這時我們需要對a進(jìn)行i次減法：f[i][0] = i;
f[0][j]表示a為空和b的前j個字符時，這時我們需要對a進(jìn)行i次加法：f[0][j] = i;

那么我們希望用之前的f來更新最新的f，我們主要分為兩種狀態(tài)；

當(dāng)i和j變更時，我們需要對a做添加或刪除：f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);

當(dāng)i和j同時變更，且a[i]==b[j],這時不需要操作：(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);
                // 最后一個數(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動態(tài)規(guī)劃篇之線性DP的示例詳解的文章就介紹到這了,更多相關(guān)Java線性DP內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: