2024/3/27打卡更小的数（十四届蓝桥杯）——区间DP

目录

题目 

思路

代码

---

题目 

思路

        题目说求数组某个区间中的数进行翻转，由于区间选择多，首先想到DP问题。

        第一版想到的方法（错误的），当进行状态计算的时候，无法判定区间是否翻转后满足要求，即反转后的值小于翻转前的值。

        其二有个错误的点，对于包含 ， 的区间  进行翻转，只能被认定作为一个方案，无法从 和  中传递过来，意思就是  区间中的区间进行翻转是与  无关的。

        看了别人的讲解后，恍然大悟。

        是一个区间动态规划问题，我们先枚举每个小区间，然后向大区间递增，大区间是否可以翻转满足要求，1.看是否右端点<左端点，2.如果右端点=左端点，看它比它小的一个区间是否可以翻转，可以，那么这个区间就可以。

        总结为：

• 
• 
• 其余情况不做处理

正确的DP分析： 

代码

import java.io.*;
 
class Main{
    static int N = 5010;
    static int n;
    static long res;
    static int[] a = new int[N];
    static int[][] f = new int[N][N];
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String s = in.readLine();
        n = s.length();
        for(int i=1;i<=n;i++) a[i] = Integer.parseInt(String.valueOf(s.charAt(i-1)));
        
        // 区间合并一般都先将小区间进行计算
        for(int len = 2;len<=n;len++){ // 枚举长度
            for(int i=1;i<=n;i++){ // 枚举左端点
                int j = i+len-1; // 右端点
                if(j>n) continue; // j<n
                if(a[j]<a[i]) f[i][j] = 1; //如果右端点小于左端点
                if(a[i]==a[j]&&f[i+1][j-1]==1) f[i][j] = 1; // 或者右端点等于左端点，但是左端点+1的数 > 右端点-1的数
                if(f[i][j]==1) res++; // 如果可以，res++
            }
        }
        System.out.println(res);
    }
}