动态规划-1

发表于 更新于 分类于 ， Valine：

什么样的问题可以使用动态规划? 通常待处理对象是一个有一定顺序的队列，可以按顺序处理队列中的元素，且处理元素得到的解只受队列前面元素的影响，而不受队列后面内容的影响。即假设有 0到n 个元素，那么，0 到 第i 个元素得出的一个答案不会受到 第 i + 1 个元素的影响。

动态规划的步骤

在撰写一个动态规划程序的时候，主要需提前做好如下准备：

  1. 状态量的定义；
  2. 初始条件；
  3. 状态转移方程；
  4. 终止条件。

下面以两个例子加以说明。

1. 例子

1.1 斐波那契数列问题

LeetCode-斐波那契数列

经典的 斐波那契数列问题。使用动态规划来解决：

  • Step1: 确定初始条件。
  • Step2: 确定动态规划公式。
  • Step3: 确定终止条件。

也就是3步：初始状态 -》 状态转移 -》 返回值。

斐波那契问题示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int fib(int n) {
        // 初始状态
        int pre1 = 0, pre2 = 1, sum;
        for(int i = 0; i < n; ++i){
            // 状态转移条件
            sum = (pre1 + pre2)%1000000007;
            // 状态转移处理
            pre1 = pre2;
            pre2 = sum;
        }
        // 返回
        return pre1;
    }
}

1.2 正则表达式匹配

LeetCode-正则表达式匹配, 题解参考

请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

Note:

  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

对于正则表达式这道题目，可以按照下面的步骤建立动态规划的状态量 及 规定状态量的转移方式。

状态定义：设动态规划矩阵 dp, dp[i][j] 代表字符串s的 前i个字符 组成的子串和 p的 前j个字符 组成的子串是否可以匹配。（需要注意的是， dp[i][j] 对应的元素分别是 s[i-1] 和 p[j-1], 例如 dp[1][1] 匹配 s[0] 和 p[0] 字串。这么做的原因是 dp[0][0] 需要去匹配空字符串。）

转移方程：

    1. 当 p[j-1] == '*' 时，dp[i][j] 在以下任一情况满足时为 true：(note:题目说明，不存在连续的 *)
    • 1.1 dp[i][j - 2] == true. 因为 p[j - 1] = '*', p[j - 2]='\w' , dp[i][j - 2] == true; 即可以认为 p[j - 2] 的字符出现0次, 从而有 dp[i][j] == true;
    • 1.2 dp[i][j - 1] == true, 可以认为 p[j - 2] 的字符出现1次。
    • 1.3 dp[i - 1][j] == true 且 s[i - 1] == p[j - 2], 即让字符 p[j - 2] 再多出现1次。
    • 1.4 dp[i - 1][j] == true, 且 p[j - 2]='.'. .* 可以匹配任意字符，因为它表示 任意字符 (.) 出现任意次数。
    1. 当 p[j] != '*' 时，dp[i][j] 在以下任意情况成立时为 true.
    • 2.1 dp[i - 1][j - 1] == true && s[i - 1] == p[j - 1]。
    • 2.2 dp[i - 1][j - 1] == true && p[j - 1] == '.';。

初始条件:

  1. dp[0][0] = true, 两个空字串可以匹配。
  2. dp[0][j] = dp[0][j-2] 且 p[j-1] = '*', s 为空字符，p 的 1, 3, 5 .. 位都为 * 即可匹配。

返回值

dp[s.length][p.length] 的值。

这题的状态转移步骤有些复杂，需要非常仔细。

这一题最需要注意和学习的点是：它的状态变量不是单维的，而是一个二维的数组！！处理其实也很简单，就是对二维量进行遍历！！

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean isMatch(String s, String p) {

        char[] sChars = s.toCharArray(), pChars = p.toCharArray();
        int slen = sChars.length, plen = pChars.length;
        boolean[][] dp = new boolean[slen+1][plen+1];
        dp[0][0] = true;
        for(int i = 2; i < plen + 1; i += 2) dp[0][i] = (dp[0][i-2] && pChars[i-1] == '*');
        for(int i = 1; i < slen + 1; i++){
            // 可以从1开始，因为如果匹配串为空，除非目标串也为空才可能为true，否则一定为 false
            for(int j = 1; j < plen + 1; j++){ 
                if(pChars[j-1] == '*'){
                    if(j >=2 && dp[i][j-2]) dp[i][j] = true;
                    if(dp[i][j-1]) dp[i][j] = true;
                    if( i > 0 && j >= 2 && dp[i-1][j] 
                    && (pChars[j-2] == sChars[i-1] || pChars[j-2] == '.')) dp[i][j] = true;
                }else{
                    if(i > 0 && dp[i-1][j-1] 
                    && (pChars[j-1] == sChars[i-1] || pChars[j-1] == '.')) dp[i][j] = true;
                }
            }
        }
        return dp[slen][plen];   
    }
}