区间DP概述（JAVA）

概述

区间DP和线性DP其实从代码角度来说就是遍历处理的顺序不一样
合并：即将两个或多个部分进行整合，也可以反过来；

特征：能将问题分解为能两两合并的形式；

求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

例题

例题一 更小的数

这个题典型的用区间DP，可以看到比大小如果首位和末位的大小确定，是否满足条件就可以确定，而大小相等的时候就需要用到前面已经得到的dp[i+1][j-1]

package com.js.datastructure.recursion.蓝桥.国特训练营.动态规划线性DP;

import java.util.Scanner;

public class 更小的数 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        //字符串长度为n
        //由数字0~9组成
        //选取子串并且把子串翻转

        //dp[i][j] 代表下标从i到j子串的个数
        String s = scanner.nextLine();
        int len = s.length();
        int t = s.length();

        boolean[][] dp = new boolean[len][len];

        int ans = 0;
        for (int i = 2; i <= t; i++) {//代表子串的长度
            for (int j = 0; j < len - i + 1; j++) {
                int k = j + i - 1;
                if(s.charAt(j) > s.charAt(j + i - 1)){
                    dp[j][k] = true;
                    ans++;
                } else if (s.charAt(j) < s.charAt(j + i - 1)) {
                    dp[j][k] = false;
                }else {
                    dp[j][k] = dp[j+1][k-1];
                    if(dp[j][k]){
                        ans++;
                    }
                }
            }
        }

        System.out.println(ans);
    }
}

例题二 能量项链

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
      //需要把v[]再复制一份（使得每个数的遍历都是数组长度）
      //例如：输入  1 2 3 4  复制成 1 2 3 4 1 2 3 4
      //状态转移方程 dp[i][j] = Math.max(dp[i][k]+dp[k+1][j]+sum(i,k,j)) (i<=k<j)
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[2*n+2];
        for(int i=1;i<=n;i++){
          arr[i] = scan.nextInt();
          arr[n+i] = arr[i];
        }
        long[][] dp = new long[2*n+2][2*n+2];
        for(int len=2;len<=n;len++){
          for(int i=1;i+len-1<=2*n;i++){
            int j=i+len-1;
            for(int k=i;k<j;k++){
              dp[i][j] = Math.max(dp[i][j],dp[i][k]+dp[k+1][j]+arr[i]*arr[j+1]*arr[k+1]);
            }
          }
        }
        long ans = 0;
        for(int i=1;i<=n;i++){
          ans = Math.max(ans,dp[i][i+n-1]);
        }
        System.out.println(ans);
        scan.close();
    }
}片