动态规划 Dynamic Program算法

Posted on | In |

动态规划英文 Dynamic Programming，是求解决策过程最优化的数学方法，后来沿用到了编程领域。

动态规划的大致思路是把一个复杂的问题转化成一个分阶段逐步递推的过程，从简单的初始状态一步一步递推，最终得到复杂问题的最优解。

动态规划解决问题的过程分为两步：

  • 寻找状态转移方程
  • 利用状态转移方程式自底向上求解问题

#5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

Example 2:
Input: “cbbd”
Output: “bb”

思路：
首先，如果一个子串 s(i, j)是一个回文，那么s[i-1]==s[j+1]的时候，我们可以推断s(i-1, j+1)也是一个回文。基于这个动态转移，我们可以推断用DP。

找到初始状态：
首先，一个字符一定是回文。
其次，两个相同的字符一定是回文。

代码如下：

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
40
class Solution {
public:
    string longestPalindrome(string s) {
        
        int n = s.size();
        if(n == 0) return s;
        
        vector<vector<int>> dp(n, vector<n, 0>); //建立dp二维表格
        int maxl = 1;
        int start = 0; //注意start和maxl必须同时进行更新
        
        //初始状态1：
        for(int i = 0; i<n; i++){
            dp[i][i] = 1;
            start = i;    
        }
        //初始状态2：
        for(int i = 0; i<n-1; i++){
            dp[i][i+1] = 1;
            maxl = 2; 
            start = i;   
        }
        
        //状态转移
        for(int k = 3; k<=n; k++){ //遍历长度 maxl
            for(int i = 0; i<n-k+1; i++){ //遍历start
                int j = i+k-1;
                if(dp[i+1][j-1] == 1 && s[i] == s[j]) {
                    dp[i][j] = 1;
                    if(k > maxl){
                        maxl = k;
                        start = i;
                    }
                }
            }
        }
        
        return s.substr(start, maxl);
    }
};

#10. Regular Expression Matching 正则表达式

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

思路：
首先想是否存在状态方程，显然是存在的。两个指针s[i]和p[j]。假设当前s(0i-1)与p(0j-1)符合正则表达式要求，那么我们只需要判断s[i]和p[j]的这个状态就好了。

那么我们来看pattern的两个字符。

  • ‘.’单个占位，表示任何字符。
  • ‘‘不占位，表示前一个字符的复制情况。分两种情况：（1）忽略前一个字符；此时你比较的是s[i]和p[j-2]（2）复制前一个字符任意次，但至少1次，那么你首先要保证 \ 前边的这个字符已经存在了，也就是验证s[i-1]和p[j]是正则的。之后再去验证s[i]是否正则。

一定要记住*不占位，他只代表重复次数。

代码：

class Solution {
public:
    bool isMatch(string s, string p) {

        int sn = s.size();
        int pn = p.size();

        //注意这里使用了多添加一个位置，来处理空字符串的情况。
        vector<vector<bool>> dp = vector(sn+1, vector<bool>(pn+1, false));

        //初始状态，两个字符串都是空的，那么肯定是正则的
        dp[0][0] = true;

        for(int i = 0; i<sn+1; i++){
            for(int j = 1; j<pn+1; j++){
                if(p[j-1] == '*'){
                //遇到'*'
                //(1)保证'*'前边的字符存在，先要验证dp[i-1][j];然后再验证s[i]是否是*前边的字符。
                //(2)'*'前边的字符不存在，那么退化
                    dp[i][j] = i && dp[i-1][j] && (s[i-1]==p[j-2] || p[j-2] == '.') || dp[i][j-2];               
                } else{
                //正常情况，正常处理。
                    dp[i][j] = i && dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1] == '.');
                }

            }
        }
        return dp[sn][pn];
    }
};