解题流程

  • 暴力搜索(自顶向下)
  • 去冗余
  • 改非递归(自底向上)

去冗余

  • 存储子问题的结果，避免重复计算


  • 解题

  • 关键 状态转移方程

LeetCode 10

  • 主串A, 模式串B
    • B最后一个字符是 正常字符，判断A[n-1]是否等于B[m-1], 相等则继续向前匹配，看动态规划 - 图1与动态规划 - 图2, 不相等就是不能匹配，这就是子问题
    • 如果B最后一个字符是 . ， 它能匹配任一字符，直接开始动态规划 - 图3与动态规划 - 图4,
    • 如果B的最后一个字符串是它代表B{m-2} =c 可以重复0次或多次，它们是一个整体c
      • A[n-1] 是0个c， B最后两个字符废掉，进行动态规划 - 图5与动态规划 - 图6的匹配
      • A[n-1]是末尾多个c的最后一个，A匹配完可以前移一个，B继续匹配动态规划 - 图7与动态规划 - 图8

  • 代码说明

    • 非递归自底向上

    • 字符串匹配从后向前

      1. class Solution {
      2. public boolean isMatch(String s, String p) {
      3.    int n = s.length();
      4.    int m = p.length();
      6.    // 用于标记 主串s的i处的字符和 模式串j处的字符是否匹配上
      7.    boolean[][] f = new boolean[n+1][m+1];
      9.    // 主串
      10.    for(int i=0; i<=n; i++) {
      11.        // 模式
      12.        for(int j=0; j<=m; j++) {
      13.            // 正则为空的情况
      14.            if(j == 0) {
      15.                // 除 i==0的情况，其他都是false
      16.                f[i][j] = i == 0;
      17.            } else {
      18.                if(p.charAt(j-1) != '*'){
      19.                    // 模式串 最后一个是 正常字符 或者 . 的情况
      20.                    if(i > 0 && (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.')) {
      21.                        // 主串 和 模式串，都往前一位，看是否匹配
      22.                        f[i][j] = f[i-1][j-1];
      23.                    }
      24.                } else {
      25.                    // 最后一位是* 的情况
      27.                    // 不看
      28.                    if(j>=2 || !(s.charAt(i-1) == p.charAt(j-2) || 
      29.                        p.charAt(j-2) == '.')) {
      30.                        // 模式串 向前 移动 两位(c*)
      31.                        f[i][j] |= f[i][j-2];
      32.                    }
      34.                    // 看 主串前移 一位
      35.                    if(i >= 1 && j >= 2 &&
      36.                        (s.charAt(i-1) == p.charAt(j-2) || 
      37.                        p.charAt(j-2) == '.'))
      38.                        f[i][j] |= f[i-1][j];
      39.                }
      40.            }
      41.        }
      42.    }
      43.    return f[n][m];
      44. }
      45. }

LeetCode 72 编辑距离

  • 步骤1. 定义数组元素的含义

dp[i][j]: word1长度i、word2长度j，将word1转为word2使用的最少操作次数

  • 步骤2. 找出 关系数组 元素间的 关系式

dp[i][j]、dp[i][j-1]、dp[i-1][j]、dp[i-1][j-1] 找这几个的关系

  • word1[i]与word2[j]相等，这时不需要进行任何操作，显然，dp[i][j] = dp[i-1][j-1]
  • word1[i]与word2[j]不相等，这时必须要进行调整，三种调整方式
    • 1.替换，将word1[i]替换成word2[j]相等，则有dp[i][j] = dp[i-1][j-1] + 1
    • 2.插入，将word1插入一个与word2[j]相等，则有dp[i][j] = dp[i][j-1] + 1
    • 3删除，如果把字符word1[i]删除，则有dp[i][j] = dp[i-1][j] + 1
    • 选择上面三种操作里面最小的 min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
      • 步骤3. 找初始值

当 i 或者 j有一个为0时，上述关系就不能用，所以初值
计算出所有的dp[0][j] 和 dp[i][0]

LeetCode 32 最长有效括号

  • 步骤1

dp[i] 位置i结尾时 ，最长的有效括号子串

  • 步骤2

      1. 如果dp[i] = a, i+1 是右括号 ) 并且 i+1-a是左括号(,那么 dp[i+1] = dp[i]+2
      1. 如果dp[i] = a, i+1 是左括号 ( 并且 i+2是右括号）,那么 dp[i+1] = 0，dp[i+2] = dp[i]+2, 并且i-1处也是有效括号，那么dp[i+2] = dp[i]+2 + dp[i-1]

  • 步骤3

初始值
i = 0 , dp[0] = 0
一直找，直到遇到第一个右括号

LeetCode 44 通配符匹配

主串s ， 模式串p

  • 步骤1

dp[i][j] 表示s在i位置和p在j位置，是否匹配

  • 步骤2
    • 从后向前匹配
    • 当s[n-1]与p[m-1]匹配时，向前找 s[n-2] 与 p[m-1] —-> dp[i][j] = dp[i-1][j-1]
    • 当p在m-1是?, s, p都向前走一位，判断s[n-2]与p[m-2] —-> dp[i][j] = dp[i-1][j-1]
    • 当p在m-1是*时, c=p[m-2]
      • 如果s[n-1] 不等于p[m-2]，没匹配上，p向前走两位，这种情况可以出现在中间位置，*可以匹配0次 dp[i][j] = dp[i][j-2]
      • 如果s[n-1]能匹配上p[m-2]，s向前移动一位，p不动，等到匹配不上时就能动了 dp[i][j] = dp[i-1][j]
  • 步骤3

初始值