Leetcode 上动态规划问题的分析（10，474，651）

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)。

Links: leetcode-上动态规划问题的总结