关于动态规划的想法

发表于 | 分类于 | 评论数： | 阅读次数：

前言

动态规划是经常用到的算法，一般是通过递推，将一个复杂的问题分解为简单的最小问题求解，即存在着最优子结构。从求解子问题一步步推出原始问题的解。我将目前遇到的动态规划的问题按照开辟数组的维度分为一维和二维两类，背包问题不属于这类，因为背包问题相关的问题也是通过动态规划，但是比较复杂，单独放在外面。以上是我个人对于遇到的动态规范的分类，纯属个人想法，还有树形动态规划，后续遇到会加入进去。

一维

这里的一维也可以理解为递推，即一个问题的求解一般根据其前一个子问题或前两子问题来的。

比如Fibonacci数列，LeetCode 70等。

以Fibonacci数列为例，$f(n) = f(n-1) + f(n-2)$,其中$f(1) = f(2) = 1$。这种问题一般通过递归自顶向下或者循环自底向上求解。如求Fibonacci数列的$f(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 自顶向下，递归
public long fibonacci(int n){
    if(n <= 2){
        return 1;
    }else{
        return fibonacci(n-1) + fibonacci(n-2)
    }
}

// 自底向上
public long fibonacci(int n){
    if(n <= 2){
        return 1;
    }
    long p = 1;q = 1;
    for(int i = 3;i <= n;i++){
        int tmp = q;
        q = p + q;
        p = tmp;
    }
    return q;
}

当然在递归时存在着重复计算，如$f(n-1)$需要计算0到n-2的所有子结果，而$f(n-2)$需要计算0到n-3的所有子结果，存在着0到n-3的子问题的重复计算。因此可以使用备忘录的形式，即开辟数组记录已经计算过的$f(n)$值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 修改之后的递归
public long fibonacci(int n){
    long[] memo = new long[n+1];
    for(int i = 0;i <= n;i++){
        memo[i] = -1;
    }
    return recursion(n);
}

public long recursion(int n){
    if(n <= 2){
        return 1;
    }
    if(memo[n] != -1){
        return memo[n];
    }
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
    return memo[n];
}

二维

二维下的动态规划，也可以看做是区间dp，一般是将问题从最小的区间开始，不断扩展，从已知的几个相邻区间推到出现区间的值。

数组从上向下或从左往右扩展

如字符串的编辑距离的求解,一开始得到各自空字符串的编辑距离（二维数组第0行和第0列），接着根据当前比较两个字符的情况和已知的区间（数组中的左元素、上元素和左上元素）得到当前区间的值。

如简单正则表达式匹配,假设$d[i][j]​$表示p字符模式从0到i的子串和s字符串从0到j的子串的匹配结果。

  • 如果$p[i]=’*’ \&\&p[i-1] = s[j]$，$d[i][j]=d[i-1][j]||d[i-2][j] || d[i][j-1]$
  • 如果$p[i]=’*’ \&\&p[i-1]\neq s[j]​$，$d[i][j]=d[i-1][j]||d[i-2][j]​$
  • 如果$p[i]=’.’ ||p[i] ==s[j]$，$d[i][j]=true$
  • 不满足上述情况的，$d[i][j]=false$

实现代码如下：s

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public boolean isMatch(String s, String p) {
    boolean[][] isMacth = new boolean[p.length()+1][s.length()+1];
    isMacth[0][0] = true;
    for(int i = 1; i <= s.length();i++){
        isMacth[0][i] = false;
    }
    for(int i = 1; i <= p.length();i++){
        if(p.charAt(i-1) == '*'){
            isMacth[i][0] = isMacth[i-2][0];
        }else {
            isMacth[i][0] = false;
        }
    }
    for(int i = 1;i <= p.length();i++){
        if(p.charAt(i-1) == '*'){
            for(int j = 1; j <= s.length();j++){
                if(compare(p.charAt(i-2), s.charAt(j-1))){
                    isMacth[i][j] = isMacth[i][j-1];
                }
                isMacth[i][j] = isMacth[i-1][j] || isMacth[i-2][j] || isMacth[i][j];
            }
        }else {
            for(int j = 1; j <= s.length(); j++){
                if (compare(p.charAt(i-1), s.charAt(j-1))){
                   isMacth[i][j] = isMacth[i-1][j-1];
                }else {
                    isMacth[i][j] = false;
                }
            }
    	}
    }
	return isMacth[p.length()][s.length()];
}
public boolean compare(char a, char b){
	if(a == '.'){
        return true;
	}else
        return a == b;
}

数组从中间向左上或右下扩展

如最长回文子串,假设$p[i][j]$表示字符串第$i$个字符到第$j$个字符之间的子串是否为回文子串，其递推公式为：
$$
p[i][j] = \begin{cases}
true \quad(s[i] == s[j]\quad and\quad p[i+1][j-1] = true)\quad or \quad j-i == 1\\
false \quad other\\
\end{cases}
$$
如果$p[i][j]$为真且长度大于当前最大长度则记录长度和起始位置。

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
26
public String longestPalindrome(String s) {
	if(s == null || s.length() <= 1){
        return s;
    }
    boolean[][] p = new boolean[s.length()][s.length()];
    p[s.length()-1][s.length()-1] = true;
    int l = 0, start = 0;
    for(int i = s.length()-2;i >= 0;i--){
    	p[i][i] = true;
        for(int j = i+1; j < s.length();j++){
        	if(s.charAt(i) == s.charAt(j)){
            	if((j-i) == 1){
                	p[i][j] = true;
                }
                if(p[i+1][j-1]){
                	p[i][j] = true;
                }
            }
            if(p[i][j] && j - i > l){
            	l = j - i;
                start = i;
            }
    	}
    }
	return s.substring(start, start+l+1);
}

背包问题

0-1背包问题及其相关的问题可以看大牛的《背包九讲》，里面写的很详细。

0%