基础题型
LeetCode练习
- 132. 分割回文串 II">典型区间思想 132. 分割回文串 II
  - 思路
- 139. 单词拆分">打表+典型区间dp139. 单词拆分
  - 思路
- 打表+dfs 140. 单词拆分 II">打表+dfs 140. 单词拆分 II
  - 思路
- 403. 青蛙过河">hashmap映射、有条件限制的区间dp 403. 青蛙过河
剑指offer
- 25. 剪绳子 - AcWing题库">dp / 找规律25. 剪绳子 - AcWing题库
- 30. 正则表达式匹配">递归实现dp/循环实现区间dp 实现30. 正则表达式匹配
  - 递归实现dp
  - 循环实现dp
- 44. 通配符匹配 ">44. 通配符匹配

基础题型

经典区间dp 合并石子

环形区间dp 环形石子合并

区间相乘dp 能量项链

区间乘积dp + 高精度凸多边形的划分

LeetCode练习

LeetCode152 https://leetcode.com/problems/maximum-product-subarray/

https://leetcode-cn.com/problems/maximal-square/

典型区间思想 132. 分割回文串 II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成

思路

分割次数就是分割部分-1，那么我们使用一个状态f[i]来表示一个方案
f[i]表示s[1~i] 划分成f[i] 个回文串
dp划分依据是 最后一次划分
那么当最后一个区间[k, j]是回文串的时候，所有区间[1, j]回文串的数量就是[1, k - 1] + 1 $区间dp - 图1$ %20)%20%5C%5C%0A#card=math&code=f%5Bi%5D%20%3D%20%5Cmin%20%28f%5Bk%20-%201%5D%20%2B%201%28k%20%3D%20%5B1%2C%20i%5D%29%20%29%20%5C%5C%0A)

再建一个g[i][j]表示 [i, j]是否为回文串

区间dp - 图2

class Solution {
    public int minCut(String s) {
        //长度为2000，使用dfs暴搜会超时
        //先打表
        s = " " + s;
        int n = s.length();
        boolean g[][] = new boolean[n][n];
        //j提前并且i+1<=j-1保证g[i+1][j-1]已经被计算过
        for (int j = 1; j < n; j ++){
            g[j][j] = true;
            for (int i = 1; i < j; i ++){
                if (s.substring(i, i + 1).equals(s.substring(j, j + 1)))
                    if (g[i + 1][j - 1] == true || i + 1 > j - 1)
                        g[i][j] = true;
            }
        }

        int[]f= new int[n];
        for (int i = 1; i < n; i ++){
            f[i] = Integer.MAX_VALUE;
            for (int k = 1; k <= i; k ++){
                if (g[k][i] == true)
                    f[i] = Math.min(f[i], f[k - 1] + 1);
            }
        }
        return f[n - 1] - 1;
    }
}

打表+典型区间dp139. 单词拆分

思路

和上一题一样，不过这道题的字符串长度比较大，使用dfs会超时

dfs打表

class Solution {
    int n; boolean flag;
    boolean[][] g; 
    public boolean wordBreak(String s, List<String> wordDict) {
        //区间dp， g[i][j]代表字符串i~j能被拆分成字典中单词
        //暴搜dfs，最多2^n,加上剪枝，
        n = s.length();
        s = " " + s; 
        g = new boolean[n + 1][n + 1];
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= i; j ++)
                if (matches(s.substring(j, i + 1), wordDict) == true){
                    g[j][i] = true;
                }
        //System.out.println(g[5][8]);
        dfs(s, 1);
        return flag;
    }
    public boolean matches(String s, List<String> wordDict){
        //System.out.println(s);
        for (String words : wordDict){
            if (words.equals(s))
                return true;
        }
        return false;
    }

//如果一直找不到，会遍历所有的情况，这样就会超时
    public void dfs(String s, int u){
         if (flag == true) return ;
        if (u == n + 1){
            flag = true;
            return;
        }
            for (int i = u; i <= n; i ++){
                if (g[u][i] == true){
                    //System.out.println(u + " " + i);
                    dfs(s, i + 1);
                }
            }
    }
}

因此我们使用区间dp

$区间dp - 图3$ %5C%5C%0Af%5B0%5D%20%3D%20true%20%5C%20%3A%20%E4%BB%A3%E8%A1%A8%E6%B2%A1%E6%9C%89%E5%AD%97%E7%AC%A6%E7%9A%84%E6%97%B6%E5%80%99%E6%98%AF%E7%AC%A6%E5%90%88%E6%9D%A1%E4%BB%B6%E7%9A%84%0A#card=math&code=f%5Bi%5D%20%E4%BB%A3%E8%A1%A8%20%5B1%EF%BC%8C%20i%5D%20%E8%83%BD%E5%A4%9F%E8%A2%AB%E6%8B%86%E5%88%86%E7%9A%84%E5%8D%95%E8%AF%8D%20%5C%5C%0A%0Af%5Bi%5D%20%3D%20f%5Bk%20-%201%5D%20%20%28%E5%A6%82%E6%9E%9C%E5%8C%BA%E9%97%B4%5Bi%2Cj%5D%20%E8%83%BD%E5%A4%9F%E8%A2%AB%E6%8B%86%E5%88%86%29%5C%5C%0Af%5B0%5D%20%3D%20true%20%5C%20%3A%20%E4%BB%A3%E8%A1%A8%E6%B2%A1%E6%9C%89%E5%AD%97%E7%AC%A6%E7%9A%84%E6%97%B6%E5%80%99%E6%98%AF%E7%AC%A6%E5%90%88%E6%9D%A1%E4%BB%B6%E7%9A%84%0A)

区间dp 打表

class Solution {
    int n; boolean flag;
    boolean[][] g; 
    public boolean wordBreak(String s, List<String> wordDict) {
        //区间dp， g[i][j]代表字符串i~j能被拆分成字典中单词
        //暴搜dfs，最多2^n,加上剪枝，
        n = s.length();
        s = " " + s; 
        g = new boolean[n + 1][n + 1];
        boolean[] f= new boolean[n + 1];
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= i; j ++)
                if (matches(s.substring(j, i + 1), wordDict) == true){
                    g[j][i] = true;
                }
        //System.out.println(g[5][8]);

        f[0] = true;
        for (int i = 1; i <= n; i ++){
            for (int k = 1; k <= i; k ++)
                if (g[k][i] == true && f[i] == false){

                    f[i] = f[k - 1];
                    //System.out.println(k + " " + i + " " + f[i]);
                }
        }
        return f[n];
    }
    public boolean matches(String s, List<String> wordDict){
        //System.out.println(s);
        for (String words : wordDict){
            if (words.equals(s))
                return true;
        }
        return false;
    }
}

简化，只需要把list转换为能判断元素是否存在的集合，即set

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //把List转换成set，就能直接判断是否包含某一个字符串
        int n = s.length();
        s = " " + s;
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] f = new boolean[n + 1];
        f[0] = true;
        for (int i = 1; i <= n; i ++){
            for (int j = 1; j <= i; j ++){
                // !f[i]表示f[i]还没有被判定为true
                if (set.contains(s.substring(j, i + 1)) && !f[i]){
                    f[i] = f[j - 1];
                    //System.out.println(i + " " + j + " " + f[j - 1] + " " +f[i]);
                }
            }
        }

        return f[n];
    }
}

打表+dfs 140. 单词拆分 II

思路

上一题dfs会超时，这题居然没有超时

但是我们还是可以优化的，把g[][]改为f[i]用于存放从 i ~ n 的数组是否可以拆分成字典。

建立set，用来代替g[][]判断子字符串是不是在字典中

class Solution {
    int n; boolean flag;
    boolean[][] g; 
    List<String> res = new ArrayList<String>();
    StringBuilder sb = new StringBuilder();
    public List<String> wordBreak(String s, List<String> wordDict) {
        //区间dp， g[i][j]代表字符串i~j能被拆分成字典中单词
        //暴搜dfs，最多2^n,加上剪枝，
        n = s.length();
        s = " " + s; 

        g = new boolean[n + 1][n + 1];
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= i; j ++)
                if (matches(s.substring(j, i + 1), wordDict) == true){
                    g[j][i] = true;
                }
        //System.out.println(g[5][8]);

        dfs(s, 1);
        return res;
    }
    public boolean matches(String s, List<String> wordDict){
        //System.out.println(s);
        for (String words : wordDict){
            if (words.equals(s))
                return true;
        }
        return false;
    }


    public void dfs(String s, int u){
        if (u == n + 1){
            res.add(sb.deleteCharAt(sb.length() - 1).toString());
            sb.append(" ");
            return;
        }
            for (int i = u; i <= n; i ++){
                if (g[u][i] == true){
                    //System.out.println(u + " " + i);
                    sb.append(s.substring(u, i + 1) + " ");
                    dfs(s, i + 1);
                    sb.delete(sb.length() - i + u - 2, sb.length());
                }
            }
    }
}

class Solution {
    int n;
    boolean[] f;
    List<String> res = new ArrayList<String>();
    HashSet<String> words = new HashSet<String>();
    public List<String> wordBreak(String s, List<String> wordDict) {

        n = s.length();
        s = s + " "; 
        for (String word : wordDict)
            words.add(word);

        f = new boolean[n + 1];
        f[n] = true;

        for (int i = n - 1; i >= 0; i --)
            for (int j = i; j < n; j ++)
                if (words.contains(s.substring(i, j + 1)) == true && f[j + 1] == true){
                    f[i] = true;
                }

        dfs(s, 0, "");
        return res;
    }

    public void dfs(String s, int u, String sb){
        if (u == n){
            res.add(sb.substring(0, sb.length() - 1));
            System.out.println(res);
            return;
        }
        for (int i = u; i < n; i ++){
            if (words.contains(s.substring(u, i + 1))  == true && f[i + 1] == true){
                dfs(s, i + 1, sb + s.substring(u, i + 1) + " ");
            }
        }
    }
}

hashmap映射、有条件限制的区间dp 403. 青蛙过河

f[i][j]代表跳到了第i块石子，从上块石子跳了j步。

由于题目条件中石子的距离最多是 2^32 - 1，直接存放肯定存不了，我们可以使用hashMap来存放石子的距离和对应的石子下标。

每一步只能递增一个单位，因此 j (每一次的步数)最多为n

当f[i][j]= ture的前提是

f[hash.get(stones[i] - j])[k] = 1(上一个状态成立)
hash.containsKey(stones[i] - j) == true（上一个是从石子跳过来的）

class Solution {
    public boolean canCross(int[] stones) {
        //区间dp
        //f[i][j] 代表跳到了第i块石子的位置，从上块石子跳了j步。
        //当f[i][j]ture 的前提是 f[i - j][k] true 并且 i - j 这个距离有对应的石子
        //第二个条件可以使用hashMap来存放距离和对应的石子下标
        //每一步只能递增一个单位，因此j最多为n
        HashMap<Integer, Integer> hash = new HashMap<Integer,Integer>();
        int n = stones.length; 
        int[][] f = new int[n + 1][n + 1];
        for (int i = 0; i < n; i ++)
            hash.put(stones[i], i);

        f[0][0] = 1;
        for (int i = 1; i < n; i ++)
            for (int j = 0; j <= n; j ++){
                for (int k = Math.max(0, j - 1); k <= Math.min(j + 1, n); k ++){
                    if (hash.containsKey(stones[i] - j) == true && f[hash.get(stones[i] - j)][k] == 1)
                        f[i][j] = 1;
                }
            }
        for (int k = 0; k <= n; k ++) 
            if ( f[n - 1][k] == 1) 
                return true;
        return false;
    }
}

剑指offer

dp / 找规律25. 剪绳子 - AcWing题库

这道题两种做法

动态规划
找规律

动态规划：

设置 dp[i]:长度为i的绳子中，将绳子剪开能得到的最大乘积

初始值为都不剪绳子的状态

for (int i = 1; i <= length; i ++)
            dp[i] = i;

那么状态转移就在于最后一次是否剪绳子

剪绳子 : dp[i]=Math.max(dp[i - j] * j, dp[i])

代码：

$区间dp - 图4$ %0A#card=math&code=o%28n%5E2%29%0A)

class Solution {
    public int maxProductAfterCutting(int length)
    {
        int[] dp = new int[length + 1];
        for (int i = 1; i <= length; i ++)
            dp[i] = i;
        dp[2] = 1; 
        for(int i = 2; i <= length; i ++){
            for (int j = 1; j < i; j++){
                dp[i] = Math.max(dp[i - j] * j, dp[i]);
            }
        }
        return dp[length];
    }
}

找规律

剪的长度n < 5, 因为 (n-3)*3>n
剪的长度n != 4 4 = 2*2
剪绳子的长度为3越多越好 3> 1 * 2

因此，我们能得出，将数length % 3, 如果余1，就取为

$区间dp - 图5$

如果余2，取

$区间dp - 图6$

$区间dp - 图7$ %0A#card=math&code=o%28logn%29%0A)

class Solution {
    public int maxProductAfterCutting(int length)
    {
        int res = 1;
        if(length == 2) return 1;
        if (length ==3) return 2;
        if (length % 3 == 1){
            res *= 4; length -= 4;
        }
        if (length % 3 == 2){
            res *= 2; length -= 2;
        }
        //length就成了3的倍数，基于3越多越好的原则，剩下的绳子都剪成3
        while (length != 0){
            length -= 3;
            res *= 3;
        }
        return res;
    }
}

递归实现dp/循环实现区间dp 实现30. 正则表达式匹配

f[i][j]: s[i],s[i + 1]…… 和 p[i],p[i + 1], ……相匹配

状态转移

如果 p[j]是正常字符， f[i][j] = s[i] == p[i] && f[i + 1][j + 1]
如果 p[j]是 ., f[i][j] = f[i + 1][j + 1]
如果 p[j + 1]是 *
1. 我们需要考虑，如果 f[i][j + 2] == true, 代表s和p匹配的时候 , p[i] 和 p[i + 1]完全可以抛弃，那么 * 就代表 p[i]出现了0次
2. 如果 f[i + 1][j]== true 就代表s和p匹配的时候，"*" 至少匹配了一个字符，此时 f[i][j] = true

递归实现dp

class Solution {
    String s, p;
    int n, m;
    boolean[][] f;
    public boolean isMatch(String s, String p) {
        //递归实现
        this.s = s; this.p = p;
        int n = s.length(), m = p.length();
        this.n = n; this.m = m;
        f = new boolean[n + 1][m + 1];
        return dp(0, 0);
    }
    public boolean dp(int x, int y){
        if (y == m) return f[x][y] = x == n;
        boolean pre_match = false;
        pre_match = x < n && (p.charAt(y) == '.' || p.charAt(y) == s.charAt(x));
       // System.out.println(pre_match);
        if (y + 1 < m && p.charAt(y + 1) == '*')
            f[x][y] = dp(x, y + 2) || pre_match && dp(x + 1, y);
        else 
            f[x][y] = pre_match && dp(x + 1, y + 1);
        return f[x][y];
    }
}

循环实现dp

状态转移同上

if (j + 1 < n && p.charAt(j + 1) == '*'){
                      f[i][j] = f[i][j - 1] || flag && i > 0 && f[i - 1][j];
}else if (i > 0)
    f[i][j] = flag && f[i - 1][j - 1];

要注意 i从0开始遍历！

这是因为，可能会用到 f[0][j](j > 0)

当p字符串以 x*开头的时候，回退到 f[0][j](j > 0)，代表两个字符串都是空，匹配结果为true

class Solution {
    public boolean isMatch(String s, String p) {
        s = " " + s; p = " " + p;
        int m = s.length(), n = p.length();
        boolean[][] f = new boolean[m][n];
        f[0][0] = true; 
        for (int i = 0; i < m; i ++)
            for (int j = 1; j < n; j ++){
                boolean flag = false;
                if (p.charAt(j) == '*'){
                    f[i][j] = f[i][j - 1];
                    continue;
                }
                if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') flag = true;
                if (j + 1 < n && p.charAt(j + 1) == '*'){
                      f[i][j] = f[i][j - 1] || flag && i > 0 && f[i - 1][j];
                }else if (i > 0)
                    f[i][j] = flag && f[i - 1][j - 1];
            }
        return f[m - 1][n - 1];
    }
}

44. 通配符匹配

和上一题不同的地方在于*的意义不同

因此有一些小的改变

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        if (n == 1 && p.charAt(0) == '*') return true;
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true; s = " " + s; p = " " + p;
        for (int i = 0; i <= m; i ++){
            for (int j = 1; j <= n; j ++){
                boolean preMatch = p.charAt(j) == '?' || p.charAt(j) == s.charAt(i);
                if (p.charAt(j) == '*'){
                    //f[i][j] = f[i][j - 1]代表匹配空、f[i][j] = f[i-1][j]代表匹配任意字符串
                    f[i][j] = f[i][j - 1] || i > 0 && f[i - 1][j];
                }else 
                    f[i][j] = preMatch && i > 0 && f[i - 1][j - 1];
            }
        }
        return f[m][n];
    }
}