1 笨笨的孩子慢慢学stay hungry stay foolish 2 学习，思考，实践，改变

0%

DP算法

发表于 更新于 分类于 Valine：

1 经典的背包问题

有n个重量和价值分别为$w_i,v_i$ 的物品，从这些物品中挑选出总重量不超过W的物品。求所有挑选方案中价值总和的最大值。

限制条件：

样例输入： n = 4, (w,v) = {(2,3) , (1,2), (3,4) , (2,2)} , w = 5 则输出是 7 （选 0、1、3号物品）

分析：

记 $dp[i+1][j]$ 是从前i个物品中挑选总重不超过j 的物品时总价值的最大值。于是有如下的递推式：

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(){
    for (int i=0; i<n; i++) {
        for (int j=0; j<=W; j++) {
            if (j<w[i]) {
                dp[i+1][j] = dp[i][j];
            }
            else{
                dp[i+1][j] = max(dp[i][j],dp[i+1][j-w[i]] + v[i]);
            }
        }
    }
    cout<<dp[n][W]<<endl;
}

2 最长公共子序列

LCS问题是经典问题。给定两个字符串 $s_1s_2s_3…s_n$ 和 $t_1t_2…t_n$ 。求出这两个字符串的最长公共子序列的长度。

输入：n=4, m=4, s=”abcd”, t=”becd”

输出：3 （“bcd”）

定义 $d p[i][j]:= s_1…s_i和t_1…t_j$ 对应的LCS的长度。

由此$s_1…s_{i+1}和t_1…t_{j+1}$ 对应的公共子序列可能是几种情况：

第一，当$s_{i+1} = t_{j+1}$ 的时候，在$s_1…s_i和t_1…t_j$ 的公共子序列末尾追加上$s_{i+1}$

不等的时候，要么是$s_1…s_i和t_1…t_{j+1}$ 的序列的公共子序列，要么就是$s_1…s_{i+1}和t_1…t_j$

故递推公式是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// input n,m
char s[MAX_N],t[MAX_N];
int dp[MAX_N+1][MAX_N+1];
void solve(){
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (s[i] == t[j]) {
                dp[i+1][j+1] = dp[i][j]+1;
            }
            else{
                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
            }
        }
    }
    cout<<dp[n][m]<<endl;
}

20200211LCS_DP

3 多重部分和

leecode39里这里暂时先不考虑将所有的可以加和的结果都存起来。我们先简单考虑能够通过给定的数组里的数，将和得到。下面的代码说明了能否通过这几个数字加和为target，是返回1，不是返回0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//DP[i+1][j] 表示用前i种数字加和成j， 需要前i-1种数字加和成 j，j-a[i], j - k *a[i]
int combinationSum(vector<int>& candidates, int target){
    int dp[candidates.size()+1][target+1]; // 注意声明大小
    //init
    for(int i=0;i < candidates.size()+1; i++) dp[0][i] = 0;
    dp[0][0] = 1;
    for(int i=0; i< candidates.size();i++){
        for (int j=0; j<= target; j++) {
            for (int k=0; k * candidates[i] <= j; k++) {
                dp[i+1][j] = dp[i][j - k*candidates[i]];
            }
        }
    }
    if (dp[candidates.size()][target]) {
        return 1;
    }
    return -1;
}

// test:  vector<int> candidates = {2,3,6,7};
// cout<<combinationSum(candidates,11)<<endl; 是-1

4 leecode100-10 正则表达式匹配

给你一个字符串s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

1
2
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
1
2
3
4
5
6
7
8
9
10
11
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

这里主要是考虑到星的匹配条件。$\operatorname{dp}[i][j]$ 是表示s的前i个能否被p的前j个匹配。

当$\mathrm{p}[\mathrm{j}]=\mathrm{s}[\mathrm{i}] 或 p[j] = “.”: \mathrm{dp}[\mathrm{i}][\mathrm{j}]=\operatorname{dp}[\mathrm{i}-1][\mathrm{j}-1]$

当$p[j] = “*”$ 时考虑两种情况：

如 （ab, abc*）

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
bool isMatch(string s,string p){
    // dp[i][j] means that s 的前i个能否被p的前j个匹配
    int sl = s.length();
    int pl = p.length();
    if(p.empty()) return s.empty();
    // init
    int dp[sl+1][pl+1];
    for (int i=0; i<=sl; i++) {
        for (int j=0; j<=pl; j++) {
            dp[i][j] = 0;
        }
    }
    dp[0][0] = 1;//dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配
    for (int j=1; j<=pl; j++) {
        if (p[j] == '*' && dp[0][j - 1]) {
            dp[0][j + 1] = 1; // here's y axis should be i+1
        }
    }
    for (int i=0; i<sl; i++) {
        for (int j=0; j<pl; j++) {
            if (s[i] == p[j] || p[j] == '.') {
                dp[i+1][j+1] = dp[i][j];
            }
            if(p[j]=='*'){
                if(p[j-1]!=s[i] && p[j - 1] != '.') dp[i+1][j+1] = dp[i+1][j-1]; //如果前一个元素不匹配且不为任意元素
                else dp[i + 1][j + 1] = (dp[i + 1][j] || dp[i][j + 1] || dp[i + 1][j - 1]);
            }
        }
    }
    return dp[sl][pl];
}

int main(){
    string s = "mississippi";
    string p = "mis*is*p*.";
    cout<<isMatch(s,p)<<endl;
    return 0;
}

5 最长有效括号

leecode100题的32题，给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。其实一看子序列长度就很像是DP题，那DP怎么定义的呢？一直觉得DP的定义找准真有点难。因为有时候定义不同，解法甚至就会不同。

DP[i] 以下标为i的字符结尾的最长有效子串长度。为什么这么定义，是因为i+1的字符是不是反括号 ) 决定了能否添加在最长子串的后面，要以i+1结尾的最长有效字符串则i+1一定是 )。以 ( 结尾的子字符串对应的 dp 数组位置上的值必定为 0 。所以说我们只需要更新 ) 在 dp 数组中对应位置的值。

1，$s[i] = ) 且 s[i-1]= ($ ，可以判断字符串类似”……()” ，那么dp[i] = dp[i-2] + 2; 这里dp[i-2] 是因为后两个字符一起判断的，加2，是因为（）的字符长度是2。

2，$s[i] = ) 且 s[i-1] = )$ , 此时字符串类似 “…. ))” ，如果 $\mathrm{s}[i-\mathrm{dp}[i-1]-1]= ($ ，则：

因为这个时候要考虑到如果倒数第二个 ) 是dp[i-1] 的最长子串的一部分。对于最后个 ) ，要匹配 dp[i-1] 最长子串的前面一个 ( 才是子串增加。而dp[i-1] 最长子串的前一个 ( 跟此时 dp[i] 的 ）匹配上了的话，就还得看 dp[i-1] 的前面是否还有以前的最长子串，就是$\mathrm{dp}[i-\mathrm{dp}[i-1]-2]$。减去2 则位置就在 $here(dp[i-1]的sub)$

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
int longestValidParentheses(string s){
    if (s == "" || s=="(" || s==")") {
        return 0;
    }
    int res = 0;
    //init
    int *dp = new int[s.size()];
    for(int i=0;i<s.size();i++) dp[i] = 0;
    //begin 注意边界
    for (int i=1; i<s.size(); i++) {
        if(s[i] == ')'){
            if(s[i-1] == '(' ){
                dp[i] = (i>=2? dp[i-2]:0) + 2;
            }
            else if(i-dp[i-1]>0 && s[i-dp[i-1]-1] == '('){
                dp[i] = dp[i-1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            //update the max
            if (dp[i] > res) {
               res = dp[i];
            }
        }
        // s[i] == '(', dp[i] = 0
        else dp[i] = 0;
    }
    return res;
}

6 最大连续序列和与接雨水

如给一个 Array： 1，-2，3，1，-1，5 。则是 8 (3, 1, -1 , 5)

分析：设 DP [k] 是表示以 k 结尾的最大的和。则递推公式为 DP [k] = max {DP [k-1] + A [k] ，A [k] }，要么是前一个连续和加上数组值（当前数组值为正），要么就是数组本身。这样最后只需要一遍遍历过去，找出以某个 k 结尾的最大和的那个 DP 值即为答案。

leecode100-42题接雨水：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

第一个for循环找每个点的左侧最大高度 left[i] = max(left[i - 1], height[i - 1]);，

第二个for循环找每个点右侧的最大高度 right[i] = max(right[i + 1], height[i + 1]);

1
2
3
4
for (int i = 0; i < n; i++) {
  int level = min(left[i], right[i]);
  water += max(0, level - height[i]);
}

7 n个骰子各个和的概率

n个骰子，掷一次，所有骰子的点数之和的所有可能出现的概率。比如3个骰子，点数可能有3，4，5，… 18，3出现的概率是$(1/6)^3$ 。

分析：n个骰子，所有可能出现的点数的总次数是$6^n$ ，点数和为k出现的概率是$times of sum(k)/(6^n)$

采用动态规划的思想进行处理，假设我们我们投掷完 n 枚骰子后总点数为 j，使用 $dp[n][j]$ 表示投完 n 枚骰子后总点数为 j 的出现次数，那么我们考虑递推关系式，投第 n 枚骰子可以由投第 n-1 枚骰子转换而来，也就是如果投第 n-1 枚骰子后总点数为 j-i (1 ≤ i ≤ 6)，那么第 n 次掷出 i 即可满足条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<double> twoDiceSum(int n){
    vector<vector<double>>dp(n+1,vector<double>(6*n+1,0));
    vector<double> ans;
    for (int i=1; i<=n; i++) {
        for (int j=i; j<=6*i; j++) {
            if (i == 1) {
                dp[i][j] = 1;
                continue;
            }
            for (int k=1; k<=6; k++) {
                if (j - k >= i-1) {
                    dp[i][j] += dp[i-1][j-k];
                }
            }
        }
    }
    for (int i=n; i<=6*n; i++) {
        ans.push_back(dp[n][i]*pow(1.0/6,n));
    }
    return ans;
}

Reference

1，《挑战程序设计》 2.3 动态规划章节

2，leecode经典100题10题，32题，39题