动态规划（DP）算法Java全解 – 三郎君的日常
三郎君的日常

Java基础 / 动态规划 · 2022年5月16日 0

动态规划（DP）算法Java全解

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。在面试笔试中动态规划也是经常作为考题出现，其中较为简单的DP题目我们应该有百分之百的把握顺利解决才可以。

动态规划定义

动态规划实际上是一类题目的总称，并不是指某个固定的算法。动态规划的意义就是通过采用递推（或者分而治之）的策略，通过解决大问题的子问题从而解决整体的做法。动态规划的核心思想是巧妙的将问题拆分成多个子问题，通过计算子问题而得到整体问题的解。而子问题又可以拆分成更多的子问题，从而用类似递推迭代的方法解决要求的问题。

动态规划的解题核心

动态规划的解题核心主要分为两步：

  1. 第一步：状态的定义
  2. 第二步：状态转移方程的定义

在这里，我们为了避免混淆用“状态”这个词来替代“问题”这个词。“问题”表示的含义类似：题目、要求解的内容、题干中的疑问句这样的概念。状态表示我们在求解问题之中对问题的分析转化。

第一步：状态的定义

有的问题过于抽象，或者过于啰嗦干扰我们解题的思路，我们要做的就是将题干中的问题进行转化（换一种说法，含义不变）。转化成一系列同类问题的某个解的情况，比如说：

题目：求一个数列中最大连续子序列的和。

我们要将这个原问题转化为：

状态定义：Fk是第k项前的最大序列和，求F1～FN中最大值。

通过换一种表述方式，我们清晰的发现了解决问题的思路，如何求出F1～FN中的最大值是解决原问题的关键部分。上述将原问题转化成另一种表述方式的过程叫做：状态的定义。这样的状态定义给出了一种类似通解的思路，把一个原来毫无头绪的问题转换成了可以求解的问题。

第二步：状态转移方程的定义

在进行了状态的定义后，自然而然的想到去求解F1～FN中最大值。这也是状态定义的作用，让我们把一个总体的问题转化成一系列问题，而第二步：状态转移方程的定义则告诉我们如何去求解一个问题，对于上述已经转换成一系列问题我们要关注的点就在于：如何能够用前一项或者前几项的信息得到下一项，这种从最优子状态转换为下一个最优状态的思路就是动态规划的核心。 
对于上面的例子题目来说，状态转移方程的定义应该是：

Fk=max{Fk-1+Ak,Ak} 
Fk是前k项的和，Ak是第k项的值

仔细思考一番，我们能够得到这样的结论，对于前k个项的最大子序列和是前k-1项的最大子序列和Fk与第k项的和、或者第k项两者中较大的。如果大家还是不能理解这个原理建议用演算纸自己计算一番，这里就不过多赘述了。这种状态转移的思路就是DP的核心。

动态规划的应用场景

看过了如何去使用动态规划，那么随之而来的问题就在于：既然动态规划不是某个固定的算法，而是一种策略思路，那么什么时候应该去使用什么时候不能用呢？答案很简短：

对于一个可拆分问题中存在可以由前若干项计算当前项的问题可以由动态规划计算。 

例题1: 数塔取数问题

一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。 
每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。

该三角形第n层有n个数字，例如：

第一层有一个数字：5

第二层有两个数字：8 4

第三层有三个数字：3 6 9

第四层有四个数字：7 2 9 5

最优方案是：5 + 8 + 6 + 9 = 28

注意:上面应该是排列成一个三角形的样子不是竖向对应的，排版问题没有显示成三角形。

状态定义: Fi，j是第i行j列项最大取数和，求第n行Fn，m（0 < m < n）中最大值。

状态转移方程：Fi，j = max{Fi-1,j-1,Fi-1,j}+Ai,jt



import java.util.Scanner;

public class Dp01 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        long max = 0;
        int[][] dp = new int[n][n];
        dp[0][0] = scan.nextInt();

        for(int i=1;i<n;i++){
            for(int j=0;j<=i;j++){
                int num = scan.nextInt();
                if(j==0){
                    dp[i][j] = dp[i-1][j] + num;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j-1],dp[i - 1][j])+num;
                }
                max = Math.max(dp[i][j],max);
            }
        }
        System.out.println(max);
    }
}

例题2:编辑距离

编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。 
例如将kitten一字转成sitting： 
sitten （k->s） 
sittin （e->i） 
sitting （->g） 
所以kitten和sitting的编辑距离是3。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。 
给出两个字符串a,b，求a和b的编辑距离。

状态定义:Fi,j表示第一个字符串的前i个字母和第二个字符串的前j个字母需要编辑的次数，求Fn,m，n和m分别是两个字符串的长度。

状态转移方程： 
当Fi,j-1=Fi-1,j时，Fi,j=Fi,j-1； 
当Fi,j-1！=Fi-1,j时，Fi,j=min{Fi-1,j-1,Fi,j-1,Fi-1,j}+1.

package com.hust0328;

import java.util.Scanner;

/**
 * Created by huststl on 2018/3/28 14:44
 * 动态规划02
 */
public class dp02 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String aStr = scan.nextLine();
        String bStr = scan.nextLine();
        int aLen = aStr.length();
        int bLen = bStr.length();
        int[][] dp = new int[aLen+1][bLen+1];
        for(int i=0;i<aLen+1;i++){
            dp[i][0] = i;
        }
        for(int i=0;i<bLen+1;i++){
            dp[0][i] = i;
        }
        for(int i=1;i<aLen+1;i++){
            for(int j=1;j<bLen+1;j++){
                if(aStr.charAt(i-1) == bStr.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        System.out.println(dp[aLen][bLen]);
    }
}

例题3:矩阵取数问题

一个N*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。例如：3 * 3的方格。

1 3 3 
2 1 3 
2 2 1

能够获得的最大价值为：11

public static void main(String[] args) {
    int n=5;

    int[][] arr={{1,3,3},{2,1,3},{2,6,1},{3,2,3}};

    printArr(arr);
    for(int i=0;i<arr.length;i++){
        for(int j=0;j<arr[0].length;j++){
            if (i==0){
                if (j==0){
                    continue;
                }else {
                    arr[i][j]=arr[i][j-1]+arr[i][j];
                }
            }else {
                if (j==0){
                    arr[i][j]=arr[i-1][j]+arr[i][j];
                }else {
                    arr[i][j]=Math.max(arr[i-1][j],arr[i][j-1])+arr[i][j];
                }
            }

        }
    }
    printArr(arr);

}
private static void printArr(int[][] dp) {
    System.out.println("--------");
    for(int i=0;i<dp.length;i++){
        for(int j=0;j<dp[0].length;j++){
            System.out.print(dp[i][j]+",");
        }
        System.out.println();
    }
    System.out.println("--------");

}

例题4:背包问题

在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数）。求背包能够容纳的最大价值。

public static void main(String[] args) {

    int[] weight = {0,2,3,1,4};
    int[] price = {0,4,2,3,2};
    int[][] F = getMaxValue(weight, price);
    System.out.println("背包承重从0到所有物品重量之和为10的承重能够达到的最大价值分别为：");
    for(int i = 0;i < F.length;i++) {
        for(int j = 0;j < F[0].length;j++)
            System.out.print(F[i][j]+"\t");
        System.out.println();
    }
}
public static int[][] getMaxValue(int[] weight, int[] value) {
    int lenRow = weight.length;
    int lenColumn = 0;
    for(int i = 0;i < weight.length;i++)
        lenColumn += weight[i];
    int[][] F = new int[lenRow][lenColumn+1]; //列值长度加1，是因为最后一列要保证重量值为lenColumn
    for(int i = 1;i < weight.length;i++) {
        for(int j = 1;j <= lenColumn;j++) {
            if(weight[i]<=j) { //重量比这个状态小，那么就能放。 那么就只是放与不放，看是放重量大，还是不放重量大
                F[i][j] = Math.max(F[i-1][j], F[i-1][j-weight[i]]+value[i]);
            }else {
                F[i][j] = F[i-1][j];//第i件物品不能放
            }
        }
    }
    return F;
}

例题5:最长递增子序列

给出长度为N的数组，找出这个数组的最长递增子序列。 
(递增子序列是指，子序列的元素是递增的） 
例如：5 1 6 8 2 4 5 10，最长递增子序列是1 2 4 5 10

package com.hust0328;

import java.util.Scanner;

/**
 * Created by huststl on 2018/3/28 15:18
 * 最长递增子序列
 */
public class Dp05 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] num = new int[n];
        for(int i=0;i<n;i++){
            num[i] = scan.nextInt();
        }
        double[] dou = new double[n+1];
        dou[0] = Integer.MIN_VALUE;
        dou[1] = num[0];
        int Len = 1;
        int p,r,m;
        for(int i=1;i<n;i++){
            p = 0;
            r = Len;
            while (p<=r){
                m = (p+r)/2;
                if(dou[m] < num[i]){
                    p = m+1;
                }else {
                    r = m-1;
                }
            }
            dou[p] = num[i];
            if(p>Len){
                Len++;
            }
        }
        System.out.println(Len);
     }
}
public static void main(String[] args) {
      int[] num = {5,1,3,6,7,2,11,8,9,4,5,10};
    //  int[] num = {6,7,7,7,8,8,7,6,5,4,7,7,6,1,2,3,1,9,9,9,9,9,1};
    //  int[] num = {1,2,3,1,3};

    //vec存放递增子序列
    List<Integer> vec=new ArrayList<>();
    //maxLen数组里存放以元素i结尾的最大递增子序列长度
    int[] maxLen=new int[num.length];

    vec.add(num[0]);
    maxLen[0]=1;
    int max=1;
    out:for(int i=1;i<num.length;i++){
        for(int j=0;j<vec.size();j++){
            //在vec中查找大于等于num[i]的第一个元素并替换掉，并更新maxLen[i]，num中第i个元素结尾的最大递增子序列长度为j+1;

            if (vec.get(j)>num[i]){
                vec.remove(j);
                vec.add(j,num[i]);
                maxLen[i]=j+1;
                // 找到后继续下一个外循环。
                continue out;
            }
        }
        //如果num[i] 比vec中所以元素都大，就添加到vec中末尾，并将maxLen[i]设置为vec的大小。
        vec.add(num[i]);
        maxLen[i]=vec.size();
        max=Math.max(max, maxLen[i]);

    }
    System.out.println(JSON.toJSON(num));

    System.out.println(vec);

    System.out.println(JSON.toJSON(maxLen));
    System.out.println(max);

    Integer[] maxArr=new Integer[max];

    int j=maxLen.length-1;

    for(int i=max-1;i>=0;i--){
        for(;j>=0;j--){
            if (maxLen[j]==i+1){
                maxArr[i]=num[j];
                break;
            }
        }
    }
    System.out.println(JSON.toJSON(maxArr));
}

例题6:最大子段和

N个整数组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。 
当所给的整数均为负数时和为0。 
例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20

package com.hust0328;
/**
 * Created by huststl on 2018/3/28 15:33
 * 最大子段和
 */
public class Dp06 {
   public static int maxSubSum1(int []a){
        int maxSum=0; int nowSum=0;
        for(int i=0;i<a.length;i++){
            nowSum=nowSum+a[i];
            if(nowSum>maxSum){//更新最大子段和
                maxSum=nowSum;
            }
            if(nowSum<0){//当当前累加和为负数时舍弃，重置为0
                nowSum=0;
            }
        }
        return maxSum;
    }
    public static void main(String[] args) {
        int a[]={-2,11,-4,13,-5,-2};
        System.out.println(maxSubSum1(a));


    }
}

例题7:最长公共子序列Lcs

给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。 
比如两个串为：

abcicba 
abdkscab

ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

package com.hust0328;

import java.util.Scanner;

/**
 * Created by huststl on 2018/3/28 15:55
 * 最长公共子序列Lcs
 */
public class Dp07 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String aStr = scan.nextLine();
        String bStr = scan.nextLine();
        int aLen = aStr.length();
        int bLen = bStr.length();
        int[][] dp = new int[aLen+1][bLen+1];
        for(int i=1;i<aLen+1;i++){
            for(int j=1;j<bLen+1;j++){
                if(dp[i - 1][j] == dp[i][j - 1] && aStr.charAt(i - 1) == bStr.charAt(j - 1)
                        && dp[i - 1][j] == dp[i - 1][j - 1]){
                    dp[i][j] = dp[i-1][j]+1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        int max = dp[aLen][bLen];
        StringBuilder sb = new StringBuilder(128);
        while (max>0){
            if(dp[aLen-1][bLen] == dp[aLen][bLen-1] && dp[aLen - 1][bLen] + 1 == dp[aLen][bLen]){
                sb.append(aStr.charAt(aLen-1));
                max--;
                aLen--;
                bLen--;
            }else {
                if(dp[aLen][bLen-1] == dp[aLen][bLen]){
                    bLen--;
                }else {
                    aLen--;
                }
            }
            System.out.println(sb.reverse().toString());
        }
    }
}
public static void main(String[] args) {
        String s2="1A2C3D4B56";
        String s1="B1D23CA45B6A";

        String[][] dp= new String[s1.length()+1][s2.length()+1];
        for(int i=0;i<=s1.length();i++)
            dp[i][0] = "";
        for(int i=0;i<=s2.length();i++)
            dp[0][i] = "";

        for(int i=1;i<=s1.length();i++){
            for(int j=1;j<=s2.length();j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1]+s1.charAt(i-1);
                }else{
                    dp[i][j] = dp[i-1][j].length()>dp[i][j-1].length()?dp[i-1][j]:dp[i][j-1];
                }
            }
        }
        printArr(dp);
        String result=dp[s1.length()][s2.length()]==""?"-1":dp[s1.length()][s2.length()];


        System.out.print(result);
    }
    private static void printArr(Object[][] dp) {
        System.out.println("--------");
        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp[0].length;j++){
                System.out.print(dp[i][j]+",");
            }
            System.out.println();
        }
        System.out.println("--------");

    }

例题8:正整数分组

将一堆正整数分为2组，要求2组的和相差最小。 
例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。

 思路：

先把数据分成两组，那么必定有一组趋近于所有数的和/2

我们可以把数的和看成包的重量，每个数看成要放入包的物体，这样就能把问题当作01背包处理，找到小于sum/2的最大放入量即可

dp[i][j]代表放入到第i个物体时背包容量为j时数的和，那么dp[i][j]大小由前一个物体放或不放决定

可以得到dp[i][j] = max(dp[i – 1][j], dp[i – 1][j-a[i]] + a[i])

最后得到dp[n][sum/2]表示较小的那一组数之和，那么两组数和之差就是(sum – dp[n][sum/2])-dp[n][sum / 2]

package com.hust0328;

import java.util.Scanner;

/**
 * Created by huststl on 2018/3/28 16:18
 * 正整数分组
 */
public class dp08 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long sum = 0,max = 0;
        int[] nums = new int[n];
        for(int i=0;i < n;i++){
            nums[i]= scan.nextInt();
            sum += nums[i];
        }
        int[] dp = new int[(int)(sum/2+1)];
        for(int i=0;i<n;i++){
            for(int j = (int) (sum / 2); j > 0; j--){
                if(j >=nums[i]){
                    dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
                }
            }

        }
        for(int i=1;i<sum/2+1;i++){
            max = max >dp[i]?max:dp[i];
        }
        System.out.println(Math.abs((sum-max)-max));

    }
}

例题9:正则匹配

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

注意：本题与主站 10 题相同：https://leetcode-cn.com/problems/regular-expression-matching/

public static boolean isMatch(String s, String p) {
        if (p.length() == 0) {
            return s.length() == 0;
        }
        if (p.length()>1 && p.charAt(1) == '*') {
            if (isMatch(s, p.substring(2))) {
                return true;
            }
            if (s.length() > 0 && comp(s,p)){
                return isMatch(s.substring(1), p);
            }
            return false;
        } else {
            if (s.length() <= 0) {
                return false;
            }
            if (!comp(s, p)) {
                return false;
            }
            return isMatch(s.substring(1), p.substring(1));
        }
    }

    private static boolean comp(String s, String p) {
        return s.charAt(0) == p.charAt(0) || p.charAt(0) == '.';
    }

    public static void main(String[] args) {
        System.out.println(isMatch("aa", "a"));
        System.out.println(isMatch("aa", "a*"));
        System.out.println(isMatch("ab", ".*"));
        System.out.println(isMatch("aab", "c*a*b"));
        System.out.println(isMatch("mississippi", "mis*is*p*."));

    }

例题10：通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3:

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

输入:
s = "acdcb"
p = "a*c?b"
输出: false
public boolean charMatch(char a, char b) {
        return a == b || b == '?';
    }    
  public boolean isMatch(String s, String p) {
        int slength = s.length(), plength = p.length();
        boolean[][] dp = new boolean[slength+1][plength+1];
        dp[0][0] = true;
        for (int j = 1; j <= plength; j++) {
            if (p.charAt(j-1) == '*') {
                dp[0][j] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= slength; i++) {
            for (int j = 1; j <= plength; j++) {
                if (p.charAt(j-1) == '*') {
                    dp[i][j] = dp[i-1][j] | dp[i][j-1];
                } else {
                    dp[i][j] = dp[i-1][j-1] && charMatch(s.charAt(i-1), p.charAt(j-1));
                }
            }
        }
        return dp[slength][plength];
    }
    public static void main(String[] args) {
        System.out.println(isMatch("aa", "*"));

        System.out.println(isMatch("abefcdgiescdfimde", "ab*cd?i*de"));

        System.out.println(isMatch("aa", "a"));

        System.out.println(isMatch("abcabczzzde", "*abc???de*"));

        System.out.println(isMatch("mississippi", "m??*ss*?i*pi"));

        System.out.println(isMatch("ab", "?*"));
        System.out.println(isMatch("", "*******"));

        System.out.println(isMatch("acdcb", "a*c?b"));

        System.out.println(isMatch("adceb", "*a*b"));
        System.out.println(isMatch("aa", "a*"));
        System.out.println(isMatch("ab", "?*"));
        System.out.println(isMatch("aab", "c*a*b"));
        System.out.println(isMatch("mississippi", "mis*is*p*"));
        System.out.println(isMatch("mississippi", "mis*is*p*?"));
        System.out.println(isMatch("aaabbbaabaaaaababaabaaabbabbbbbbbbaabababbabbbaaaaba", "a******b"));
        System.out.println(isMatch("abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb",
            "**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"));

    }

您可能还喜欢...

发表评论