day-06 构造有效字符串的最少插入数

思路
动态规划：
Word[i]单独组成abc
如果Word[i]>word[i-1] 则word[i]和word[i-1]一起构成abc

解题方法
关系式：dp[i]=dp[i-1]+2或dp[i]=dp[i-1]-1

时间复杂度： O(n)

空间复杂度： O(1)

Code

class Solution {

    /*动态规划：1.Word[i]单独组成abc
    *          2.如果Word[i]>word[i-1] 则word[i]和word[i-1]一起构成abc
    * 
     */
    public int addMinimum(String word) {

        int n = word.length();
        int[] d = new int[n + 1];
        for (int i = 1; i <= n; i++) {

            d[i] = d[i - 1] + 2;
            if (i > 1 && word.charAt(i - 1) > word.charAt(i - 2)) {

                d[i] = d[i - 1] - 1;
            }

        }
        return d[n];
    }
}

注：脑子没转过来，看了题解。。。。。。

原文链接: https://blog.csdn.net/qq_53568730/article/details/135538868

day-06 构造有效字符串的最少插入数

目录