动态规划——区间型

本是古典何须时尚 2023-07-01 13:00 22阅读 0赞

# 区间型 #

--------------------

## 目录 ##

1.  概述
2.  最长的回文序列
3.  取数是否必胜

--------------------

### 1. 概述 ###

1.  给定一个序列/字符串，进行一些操作，最后一步会将序列/字符串去头/去尾
2.  剩下的会是一个区间\[i, j\]
3.  状态自然定义为f\[i\]\[j\]，表示面对子序列\[i, …, j\]时的最优性质

--------------------

### 2. 最长的回文序列 ###

##### 1. 题目描述 #####

1. 给定一个字符串S，长度是N，找到它最长的回文子序列的长度
    	例子：

输入：“bbbab”  
输出：4 (“bbbb”)

##### 2. 思路 #####

1.  确定状态  
    1. 最优策略产生的最长的回文子串T，长度是M  
    2. 情况一：回文串长度是1，即一个字母  
    3. 情况二：回文串长度大于1，那么必定有T\[0\]=T\[M-1\]  
    4. 设T\[0\]是S\[i\]，T\[M-1\]是S\[j\]，T剩下的部分T\[1…M-2\]仍然是一个回文串，而且是S\[i+1…j-1\]的最长回文串  
    5. 所以要求S\[i…j\]的最长回文子串，如果S\[i\]=S\[j\]，需要知道S\[i+1…j-1\]的最长回文子串  
    6. 否则答案是S\[i+1…j\]的最长回文子串或者S\[i…j-1\]的最长回文子串
2.  转移方程  
    状态：设f\[i\]\[j\]=为S\[i…j\]的最长回文子串的长度
3.  初始条件和边界情况  
    初始条件  
    1. f\[0\]\[0\]=f\[1\]\[1\]=…=f\[N-1\]\]\[N-1\]=1，一个字母也是一个长度为1的回文串  
    2. 如果S\[i\] = S\[i+1\]，f\[i\]\[i+1\] = 2  
    3. 如果S\[i\] != S\[i+1\]，f\[i\]\[i+1\] = 1
4.  计算顺序  
    1. 区间型动态规划不能按照 i 的顺序去计算，要按照长度 j-i 从小到大的顺序去算
    
        长度1：f[0][0],f[1][1],....f[N-1][N-1]
         	长度2：f[0][1],f[1][2],....f[N-2][N-1]
         	...
         	长度N：f[0][N-1]
         	答案是 f[0][N-1]

##### 3. 代码实现 #####

public static int longestPalindromeSubseq(String ss) {
            char[] s = ss.toCharArray();
            int n = s.length;
            if (n == 0) {
                return 0;
            }
            if (n == 1) {
                return 1;
            }
            int[][] f = new int[n][n];
            for (int i = 0; i < n; i++) {
                f[i][i] = 1;
            }
            for (int i = 0; i < n - 1; i++) {
                f[i][i + 1] = s[i] == s[i + 1] ? 2 : 1;
            }
            //len表示子串长度
            for (int len = 3; len <= n; len++) {
                for (int i = 0; i <= n - len; i++) {
                    int j = i + len - 1;
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                    if (s[i] == s[j]) {
                        f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + 2);
                    }
                }
            }
            return f[0][n - 1];
        }

--------------------

### 3. 取数是否必胜 ###

##### 1. 题目描述 #####

1.  给定一个序列a\[0\]，a\[1\]，…，a\[N-1\]，两个玩家轮流取数，每人每次只能取第一个数或者最后一个数，问先手是否必胜（如果数字一样，也算先手胜）  
    例子：  
    输入：\[1, 5, 233, 7\]  
    输出：True（先手取走1，无论后手取哪个，先手都能取走233）

##### 2. 思路 #####

1.  确定状态  
    1. 设已方数字和是A，对手数字和是B，目标是A>=B，等价于A-B>=0，也就是说已方和对手都存在着自己的数字和与对手的数字和之差，分别记为Sa=A-B，Sb=B-A  
    2. 当已方取走一个数字m后，对于已方来说，Sa=-Sb+m，现在已方有两种选择，取第一个数字m1或最后一个数字m2，为了最大化Sa，应该选择较大的那个Sx  
    3. 如果A第一个取走a\[0\]，则B面对a\[1,…N-1\]，B的最大数字差是Sb，A的数字差是a\[0\]-Sb  
    4. 如果A第一步取走a\[N-1\]，B面对a\[0,…,N-2\]，B的最大数字差Sb，A的数字差是a\[N-1\]-Sb  
    5. 当B面对a\[1…N-1\]，B这时是先手，但此时数字少了一个
2.  转移方程  
    状态：设f\[i\]\[j\]为一方先手在面对a\[i…j\]这些数字时，能得到的最大的与对手的数字差  
    ![在这里插入图片描述][20200130202512652.png]
3.  初始条件和边界情况  
    初始条件  
    1. 只有一个数字a\[i\]时，已方得a\[i\]分，对手0分，数字差为a\[i\]，即f\[i\]\[i\]=a\[i\]
4.  计算顺序  
    1. 区间型动态规划不能按照 i 的顺序去计算，要按照长度 j-i 从小到大的顺序去算  
    长度1：f\[0\]\[0\],f\[1\]\[1\],…f\[N-1\]\[N-1\]  
    长度2：f\[0\]\[1\],f\[1\]\[2\],…f\[N-2\]\[N-1\]  
    …  
    长度N：f\[0\]\[N-1\]  
    答案是如果 f\[0\]\[N-1\]>=0，先手必胜，否则必输

##### 3. 代码实现 #####

public static boolean firstWillWin2(int[] A) {
            int n = A.length;
            int[][] f = new int[n][n];
            for (int i = 0; i < n; i++) {
                f[i][i] = A[i];
            }
            for (int len = 2; len <= n; len++) {
                for (int i = 0; i <= n - len; i++) {
                    int j = i + len - 1;
                    f[i][j] = Math.max(A[i] - f[i + 1][j], A[j] - f[i][j - 1]);
                }
            }
            return f[0][n - 1] >= 0;
        }

--------------------

### 4. 判断一个字符串T是否由S变换而来 ###

##### 1. 题目描述 #####

1.  给定一个字符串S，按照树结构每次二分成左右两个部分，直至单个字符，在树上某些节点交换左右儿子，可以形成新的字符串
2.  判断一个字符串T是否由S经过这样变换而成
    
    例子：  
    输入：S=“great” T=“rgtae”  
    输出：True

##### 2. 思路 #####

1.  确定状态
    
    1.  如果T长度和S长度不一样，那么肯定不能由S变成而来
    2.  如果T是S变换而来的，并且知道S最上层二分被分成S=S1S2，那么一定有：  
        1. T也有两部分T=T1T2，T1是S1变换而来的，T2是S2变换而来的  
        2. T也有两部分T=T1T2，T1是由S2变换而来的，T2是由S1变换而来的
    3.  要求T是否由S变换而来的  
        1. 需要知道T1是否由S1变换而来的，T2是否由S2变换而来的  
        2. 需要知道T1是否由S2变换而来的，T2是否由S1变换而来的
    4.  S1,S2,T1,T2长度更短，即为子问题
2.  转移方程
    
    1.  状态：设f\[i\]\[j\]\[k\]\[h\]表示T\[k…h\]是否由S\[i…j\]变换而来
    2.  这里所有的串都是S和T的子串，且长度一样，所以每个串都可以用（起始位置，长度）表示  
        例如：  
        S1长度是5，在S中位置7开始  
        T1长度是5，在T中位置0开始  
        可以用f\[7\]\[0\]\[5\]=Ture/False表示S1能否通过变换成为T1
    3.  状态：设f\[i\]\[j\]\[k\]表示S1能否通过变换成为T1  
        1. S1为S从字符串i开始的长度为k的子串  
        2. T1为T从字符串j开始的长度为k的子串
3.  初始条件和边界情况  
    初始条件  
    1. 如果S\[i\]=T\[j\]，f\[i\]\[j\]\[1\]=true，否则f\[i\]\[j\]\[1\]=false
4.  计算顺序  
    1. 按照k从小到大的顺序进行计算  
    f\[i\]\[j\]\[1\], 0<=i<N, 0<=j<N  
    f\[i\]\[j\]\[2\], 0<=i<N-1, 0<=j<N-1  
    …  
    f\[0\]\[0\]\[N\]  
    答案是：f\[0\]\[0\]\[N\]

##### 3. 代码实现 #####

public static boolean isScramble(String ss1, String ss2) {
            char[] s1 = ss1.toCharArray();
            char[] s2 = ss2.toCharArray();
            int n = s1.length;
            int m = s2.length;
            if (n != m) {
                return false;
            }
    
            boolean[][][] f = new boolean[n][n][n + 1];
    
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    f[i][j][1] = s1[i] == s2[j];
                }
            }
    
            for (int len = 2; len <= n; len++) {
                for (int i = 0; i <= n - len; i++) {
                    for (int j = 0; j <= n - len; j++) {
                        f[i][j][len] = false;
                        for (int w = 1; w <= len - 1; w++) {
                            if (f[i][j][w] && f[i + w][j + w][len - w]) {
                                f[i][j][len] = true;
                            }
                        }
    
                        for (int w = 1; w <= len - 1; w++) {
                            if (f[i][j + len - w][w] && f[i + w][j][len - w]) {
                                f[i][j][len] = true;
                            }
                        }
                    }
                }
            }
            return f[0][0][n];
        }

[20200130202512652.png]: https://img-blog.csdnimg.cn/20200130202512652.png