Leetcode 上动态规划问题的分析(10,474,651)

Tag: leetcode 动态规划  Posted on 2020-03-11 16:57:57 Edited on 2020-04-12 19:13:31

474. Ones and Zeroes

状态:由剩余未选择过的字符串个数,剩余未用的 0 的个数以及剩余未用的 1 的个数决定,因此 dp 数组是一个三维数组。

选择:每次首先判断能否构造出当前字符串,选择值大的那个。

代码:

int[][][] dp = new int[m+1][n+1][size+1];
for(int i=0;i<=m;i++) {
    for(int j=0;j<=n;j++) {
        for(int k=1;k<=size;k++) {
            if(strings[k].zero <= i && strings[k].one <= j) {
                dp[i][j][k] = dp[i-strings[k].zero][j-strings[k].one][k-1]+1;
            }
            dp[i][j][k] = Math.max(dp[i][j][k], dp[i][j][k-1]);
        }
    }
}
return dp[m][n][size];

10. Regular Expression Matching

状态:dp[i][j] 是一个布尔数组,表示 string[i:] 和 pattern[j:] 能否匹配成功。

选择:对于 pattern 中的字母和 . 并没有选择可言;对于 *,我们可以选择匹配其之前的字母 0~N 次,放到递归中则是匹配或者不匹配。

  1. 匹配:则 pattern 保持不变,string 进一位。
  2. 不匹配,则 string 保持不变,pattern 进两位(因为 * 和其之前的字符为一个整体)。

注意:

  1. 为了代码的可读性,使用一个专门的布尔数组来记录 memory 中是否有之前计算过的值。
  2. 注意需要妥善处理边界情况。

代码:

class Solution {
    String s, p;
    boolean[][] data;
    boolean[][] computed;
    public boolean isMatch(String s, String p) {
        this.s = s;
        this.p = p;
        data = new boolean[s.length()+1][p.length()+2];
        computed = new boolean[s.length()+1][p.length()+2];
        return dp(0, 0);
    }

    private boolean dp(int i, int j) {
        // When pattern is over, return true if the string also is over.
        if(j>=p.length()) return i>=s.length();
        boolean current = false;
        if(i<s.length()) {
            if(computed[i][j]) return data[i][j];
            current = (s.charAt(i) == p.charAt(j)) || (p.charAt(j) == '.');
        }
        // Notice the * pattern must act with its previous character.
        if(p.length() > j+1 && p.charAt(j+1) == '*') data[i][j] = dp(i, j+2) || (current && dp(i+1, j));
        else data[i][j] = current && dp(i+1, j+1);
        computed[i][j] = true;
        return data[i][j];
    }
}

651. 4 Keys Keyboard

第一种思路

状态:首先有剩余的按键次数,其次是缓冲区中的字符数以及屏幕上已有的字符数。

选择:4 种按键即 4 种选择。

注意: 该思路复杂度太高 > O(N^3)。

第二种思路

状态:经过分析,最优操作只有两种情况,当 N 比较小时,全部按 A,否则是前面全按 A,后面为 选择-复制,粘贴*n,也即每次选择复制后必跟着 n 次粘贴操作(n>0)。我们设前面按的 A 的个数为 i,总操作数为 j, 则 dp(i,j) 表示该情况下 A 的最大量。

选择:选择-复制 or 粘贴。

总结

动态规划为题本质上为暴力枚举 + 剪枝。 第二种思路减去了大量在后期选择 A 的决策分支,从而降低算法的时间复杂度至 O(n^2)。