DP学习总结

,

概念

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。动态规划是一种分阶段求解决策问题的数学思想。

入门

一维消消乐
这题主要思想是将珠子分为两种状态，一种是已经和前面消掉，另一种是不消

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*************************************************************************
 > File Name:
 > Author:
 > Mail: lancelot_hcs@qq.com
 > Time: 9102
 > Desc:
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;                             
const int maxn = 1005;
ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


ll dp[10010][2], n, m, a[100005], ans = 0; //1代表和前面组合，0代表没有
int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
    }
    for (int i = 2; i <= n ; i++)
    {
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
        dp[i][1] += dp[i - 1][0] + a[i] * a[i - 1];
    }
    cout << max(dp[n][0], dp[n][1]) << endl;
    return 0;
}

字符串与dp

最大子段和

  • 概念：

给定一个由数字组成的序列，其中连续的一段子序列称为一个子段，子段中的所有数之和称为子段和，这里只考虑非空子段，即至少包含一个元素的子段。

对于有正数的序列，考虑以每一个点为结尾的最大子段和，这个子段一定满足其前缀和均非负，因为如果有一个前缀是负的，那么减掉这个前缀对于这个点一定更优，并且这个子段要尽量往前延伸。

所以我们可以只用一次扫描，记录目前统计的和 sumsum 以及答案 ansans 。当 sumsum 加上当前位置这个数还是正数的时候就继续累加 sumsum ，否则就将 sumsum 置为 00 。这样就舍掉了所有前缀是负数的情况，并且保证了这个子段尽可能的长了，也就是说扫描中记录的 sumsum 就是以每一个点为结尾的最大子段和，每一次如果 sumsum 比 ansans 大就可以更新 ansans 。最后 ansans 就是整体的最大子段和。

时间复杂度 O(N)\mathcal{O}(N)

  • 代码实现：
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*************************************************************************
 > FileName:
 > Author:      huangchangsheng
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;                             //int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1005;
int a[maxn];
ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main()
{
    int n, ans = -INF;
    n = read();
    for (int i = 0; i < n; i++)
        a[i] = read();
    ans = *max_element(a, a + n);
    if (ans < 0)
    {
        cout << ans << endl;
        return 0;
    }
    else
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            if (sum + a[i] < 0)
            {
                sum = 0;
            }
            else
            {
                sum += a[i];
            }
            ans = max(ans, sum);
        }
    }
    cout << ans << endl;
    return 0;
}

LIS

  • 概念：
    最长上升子序列，又称 LIS（Longest Increasing Subsequence）是动态规划的一个经典应用。

在原序列取任意多项，不改变他们在原来数列的先后次序，得到的序列称为原序列的先后次序，得到的序列称为原序列的子序列(subsequence)

  • 状态转移方程：

dp[i]=max(dp[i],dp[j]+1),1≤j<i && a[j]<a[i]\displaystyle dp[i] = max(dp[i], dp[j]+1) , 1 \leq j < i\ &amp;&amp;\ a[j] < a[i]

  • 代码实现：
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*************************************************************************
 > FileName:
 > Author:      huangchangsheng
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;                             //int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1005;
int a[maxn], dp[maxn], ans;
ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main()
{
    int n = read();

    for (int i = 1; i <= n; i++)
        a[i] = read();

    for (int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[i] > a[j])
                dp[i] = max(dp[i], dp[j] + 1);
        ans = max(ans, dp[i]);
    }

    cout << ans << endl;
    return 0;
}
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
//From - Milky Way

#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;

int d[100], c[100], a[100], len = 1;

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%d", &a[i]);
    }

    d[1] = a[1], c[1] = 1;
    for (int i = 2; i <= n; ++ i)
    {
        if (d[len] <= a[i])
        {
            d[++ len] = a[i], c[i] = len;
        }
        else
        {
            int j = upper_bound(d + 1, d + len + 1, a[i]) - d;
            d[j] = a[i], c[i] = j;
        }
    }

    printf("%d\n", len);

    return 0;
}

//最长不下降之输出子序列 - NlogN

原理：len在遍历时是只会越来越长的，upper_bound()二分查找上界。
二分实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int binSearch(int *array, int x, int head, int tail) //循环版本
{
    while(head <= tail)
    {
        int mid = (head + tail) / 2;
        if(List[mid] == x)
            return mid;
        else if(List[mid] > x) //注意别写反
        {
            tail = mid - 1;
        }
        else
        {
            head = mid + 1;
        }
    }
    return -1;
}

上界函数实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int mylower_bound(int *array, int size, int key)
{
    int first = 0, middle, last = size - 1;
    while(first < last)
    {
        middle = (first + last) >> 1;
        if(array[middle] < key ) //当middle小于要找的位置 ， first +1 也不会超过key的位置，最多相同
            first = middle + 1;
        else
            last = middle ; //middle有可能等于要找的位置 ， last = middle ， 用first不断逼近

    }
    return first;
}

最长公共子序列lcs

  • 概念：
    给定s1,s2,找到他们最长的公共子序列s3
  • 转移方程
    若s1[i]==s2[j]s1[i] == s2[j],则lcs[i][j]=lcs[i−1][j−1]+1lcs[i][j] = lcs[i - 1][j - 1] + 1
    若s1[i]!=s2[j]s1[i] !=s2[j],则lcs[i][j]=max(lcs[i][j−1],lcs[i−1][j])lcs[i][j] = max(lcs[i][j - 1], lcs[i - 1][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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*************************************************************************
 > FileName:
 > Author:      huangchangsheng
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;                             //int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1005;
int a[maxn], dp[maxn][maxn], ans;

int main()
{
    string s1, s2;
    int l1, l2;
    cin >> s1 >> s2;
    for (int i = 1; i <= s1.size(); i++)
    {
        for (int j = 1; j <= s2.size(); j++)
        {
            if(s1[i - 1] == s2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << dp[s1.size()][s2.size()] <<endl;
    return 0;
}

回文串

  • 原字符串与倒序后的字符串取最大公共子序列
  • 长度之差即是结果
  • 用到了reverse()函数
  • 代码实现：
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*************************************************************************
 > FileName:
 > Author:      huangchangsheng
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 把原字符串倒序，取最大公共子序列，然后。。。
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;                             //int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 3005;
int a[maxn], dp[maxn][maxn], ans;

int main()
{
    string s1, s2;
    int l1, l2;
    cin >> s1;
    s2 = s1;
    reverse(s2.begin(), s2.end());
    for (int i = 1; i <= s1.size(); i++)
    {
        for (int j = 1; j <= s2.size(); j++)
        {
            if(s1[i - 1] == s2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << s1.size() - dp[s1.size()][s1.size()] << endl;
    return 0;
}

编辑距离

  • 删除，替换，增加
  • 转移方程：

{f(i,j)={f(i−1,j−1),S[i]=T[j]min(f(i−1,j−1),f(i−1,j),f(i,j−1))+1,S[i]≠T[j] \begin{cases} f(i, j) =\end {cases}\begin{cases} f(i - 1, j - 1), { S[i] = T[j] } \\ min(f(i - 1, j -1), f(i - 1, j), f(i, j -1)) + 1,{S[i] \neq T[j]} \end{cases}

{f(0,j)=jf(i,0)=i\begin{cases} f(0, j) = j \\ f(i, 0) = i \end{cases}

  • 代码实现：
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
#include <iostream>
#include <string>
using namespace std;
int dp[110][110];
string a, b;
int main() {
    cin >>a >> b;
    int lena = a.size();
    int lenb = b.size();
    for (int i = 1; i <= lena; i++)
    {
        dp[i][0] = i;
    }
    for (int i = 1; i <= lenb; i++)
    {
        dp[0][i] = i;
    }
    for (int i = 1; i <= lena; i++)
    {
        for (int j = 1; j <= lenb; j++)
        {
            if (a[i - 1] == b[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else
            {
                dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    cout << dp[lena][lenb] <<endl;
    return 0;
}

背包问题 有空再补吧