动态规划(下篇)

逃离我推掉我的手 2023-10-04 18:34 19阅读 0赞

第七题: 回文串的分割

[分割回文串-ii\_牛客题霸\_牛客网][-ii]

### 描述 ###

给出一个字符串s，分割s使得分割出的每一个子串都是回文串

计算将字符串s分割成回文分割结果的最小切割数

例如:给定字符串s="aab",

返回1，因为回文分割结果\["aa","b"\]是切割一次生成的。

### 示例1 ###

输入："aab"

复制返回值：1

问题: 求s的最小的分割次数

**状态F(i): s的前i个字符最小的分割次数**

**状态转移方程:**

**情况1: 当F(i):(1,i)本身就是回文串时,不需要分割,返回0**

**情况2: F9i)不是回文串,但是在 j < i && \[ j+1, i \] 是回文串,则返回 min( F(i), F(j) + 1))**

**比如 aab 中F(3) 不是回文串,但是 F(2) = aa && \[3\] = b 则返回 F(2) + 1**

**初始状态: F(i) = i - 1 (就是把字符串切割成单个字符,所需 i - 1 步)**

**返回结果: F(n)**

![30d45c7dec54417f9601961e3d9cce1e.png][]

public class Solution {
            //判断是否回文串
            public boolean isPal(String s, int start, int end){
                while(start < end){
                    if(s.charAt(start) != s.charAt(end))
                        return false;
                    ++start;
                    --end;
                }
                return true;
            }
            public int minCut(String s) {
                int len = s.length();
                if(len == 0)
                    return 0;
                int[] minCut = new int[len + 1];
                // F(i)初始化
                // F(0）= -1，必要项，如果没有这一项，对于重叠字符串“aaaaa”会产生错误的结果
                for(int i = 0; i <= len; ++i){
                    minCut[i] = i - 1;
                }
                for(int i = 1; i <= len; ++i){
                    for(int j = 0; j < i; ++j){
                        // F(i) = min{F(i), 1 + F(j)}, where j<i && j+1到i是回文串
                        // 从最长串判断，如果从第j+1到i为回文字符串
                        // 则再加一次分割，从1到j，j+1到i的字符就全部分成了回文字符串
                        if(isPal(s, j, i - 1)){
                            minCut[i] = Math.min(minCut[i], minCut[j] + 1);
                        }
                    }
                }
                return minCut[len];
            }
        }

第八题: 编辑距离

[编辑距离\_牛客题霸\_牛客网][Link 1]

### 描述 ###

给定两个单词word1和word2，请计算将word1转换为word2至少需要多少步操作。  
你可以对一个单词执行以下3种操作：  
a）在单词中插入一个字符  
b）删除单词中的一个字符  
c）替换单词中的一个字符

输入："ab","bc"

返回值：2

解题思路

状态：  
子状态：**word1的前1，2，3，...m个字符转换成word2的前1，2，3...n个字符需要的编辑距离 F(i,j):word1的前i个字符于word2的前j个字符的编辑距离**  
状态递推：  
 **F(i,j) = min \{ F(i-1,j）+1, F(i,j-1) +1, F(i-1,j-1) +(w1\[i\]==w2\[j\]?0:1) \}  
上式表示从删除，增加和替换操作中选择一个最小操作数  
F(i-1,j): w1\[1,...,i-1\]于w2\[1,...,j\]的编辑距离，删除w1\[i\]的字符--->F(i,j)  
F(i,j-1): w1\[1,...,i\]于w2\[1,...,j-1\]的编辑距离，增加一个字符--->F(i,j)  
F(i-1,j-1): w1\[1,...,i-1\]于w2\[1,...,j-1\]的编辑距离，如果w1\[i\]与w2\[j\]相同**，  
不做任何操作，编辑距离不变，如果w1\[i\]与w2\[j\]不同，替换w1\[i\]的字符为w2\[j\]--->F(i,j)  
初始化：  
初始化一定要是确定的值，如果这里不加入空串，初始值无法确定  
F(i,0) = i :word与空串的编辑距离，删除操作  
F(0,i) = i :空串与word的编辑距离，增加操作  
返回结果：F(m,n)

![3efcf1dd7c05453e893bacd9497e8066.png][]

public class Solution {
            public int minDistance(String word1, String word2) {
                // word与空串之间的编辑距离为word的长度
                if(word1.isEmpty() || word2.isEmpty())
                    return Math.max(word1.length(), word2.length());
                int len1 = word1.length();
                int len2 = word2.length();
                int[][] minDis = new int[len1 + 1][len2 + 1];
                // F(i,j)初始化
                for(int i = 0; i <= len1; ++i){
                    minDis[i][0] = i;
                }
                for(int i = 0; i <= len2; ++i){
                    minDis[0][i] = i;
                }
                for(int i = 1; i <= len1; ++i){
                    for(int j = 1; j <= len2; ++j){
                    // F(i,j) = min { F(i-1,j）+1, F(i,j-1) +1, F(i-1,j-1) +(w1[i]==w2[j]?0:1) }
                    minDis[i][j] = 1 + Math.min(minDis[i - 1][j]
                            , minDis[i][j - 1]);
                    // 判断word1的第i个字符是否与word2的第j个字符相等
                    if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                        // 字符相等，F(i-1,j-1)编辑距离不变
                        minDis[i][j] = Math.min(minDis[i][j]
                                ,minDis[i - 1][j - 1]);
                    }
                    else{
                    // 字符不相等，F(i-1,j-1)编辑距离 + 1
                        minDis[i][j] = Math.min(minDis[i][j]
                                ,minDis[i - 1][j - 1] + 1);
                    }
                }
            }
            return minDis[len1][len2];
        }
    }

第九题: 不同子序列

[不同的子序列\_牛客题霸\_牛客网][Link 2]

### 描述 ###

给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？

字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符（例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）  
例如：

S="nowcccoder", T = "nowccoder"

返回 3

**解题模板(四板斧)**

问题翻译：S有多少个不同的子串与T相同  
S\[1:m\]中的子串与T\[1:n\]相同的个数  
由S的前m个字符组成的子串与T的前n个字符相同的个数  
**状态：  
子状态：由S的前1,2,...,m个字符组成的子串与T的前1,2,...,n个字符相同的个数  
F(i,j): S\[1:i\]中的子串与T\[1:j\]相同的个数  
状态递推：  
在F(i,j)处需要考虑S\[i\] = T\[j\] 和 S\[i\] != T\[j\]两种情况  
当S\[i\] = T\[j\]:  
1>: 让S\[i\]匹配T\[j\]，则  
F(i,j) = F(i-1,j-1)  
2>: 让S\[i\]不匹配T\[j\],则问题就变为S\[1:i-1\]中的子串与T\[1:j\]相同的个数，则  
F(i,j) = F(i-1,j)  
故，S\[i\] = T\[j\]时，F(i,j) = F(i-1,j-1) + F(i-1,j)  
当S\[i\] != T\[j\]:  
问题退化为S\[1:i-1\]中的子串与T\[1:j\]相同的个数  
故，S\[i\] != T\[j\]时，F(i,j) = F(i-1,j)  
初始化： 引入空串进行初始化  
F(i,0) = 1 ---> S的子串与空串相同的个数，只有空串与空串相同. F(0,j) = 0 ( j != 0)  
返回结果： F(m,n)**

![867aecaa4f474a05b0672b8c7b85fd3c.png][]

public int numDistinct(String S, String T) {
            int sLen = S.length();
            int tLen = T.length();
            int[][] numDis = new int[sLen + 1][tLen + 1];
            numDis[0][0] = 1;
            // F(i,j)，初始化第一行剩余列的所有值为0
            for(int i = 1; i <= tLen; ++i){
                numDis[0][i] = 0;
            }
            //F(i, 0) = 1
            for(int i = 1; i <= sLen; ++i){
                numDis[i][0] = 1;
            }
            for(int i = 1; i <= sLen; ++i){
                for(int j = 1; j <= tLen; ++j){
                    // S的第i个字符与T的第j个字符相同
                    if(S.charAt(i - 1) == T.charAt(j - 1)){
                        numDis[i][j] = numDis[i - 1][j] + numDis[i - 1][j - 1];
                    }
                    else{
                        // S的第i个字符与T的第j个字符不相同
                        // 从S的前i-1个字符中找子串，使子串与T的前j个字符相同
                        numDis[i][j] = numDis[i - 1][j];
                    }
                }
            }
            return numDis[sLen][tLen];
        }
    }

[-ii]: https://www.nowcoder.com/practice/1025ffc2939547e39e8a38a955de1dd3?tpId=46&tqId=29048&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
[30d45c7dec54417f9601961e3d9cce1e.png]: https://img-blog.csdnimg.cn/30d45c7dec54417f9601961e3d9cce1e.png
[Link 1]: https://www.nowcoder.com/practice/81d7738f954242e5ade5e65ec40e5027?tpId=46&tqId=29106&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
[3efcf1dd7c05453e893bacd9497e8066.png]: https://img-blog.csdnimg.cn/3efcf1dd7c05453e893bacd9497e8066.png
[Link 2]: https://www.nowcoder.com/practice/ed2923e49d3d495f8321aa46ade9f873?tpId=46&tqId=29065&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
[867aecaa4f474a05b0672b8c7b85fd3c.png]: https://img-blog.csdnimg.cn/867aecaa4f474a05b0672b8c7b85fd3c.png