云曦

Choice is more important than effort

0%

动态规划常见模型

发表于 分类于
本文字数： 4.1k 阅读时长 ≈ 4 分钟

LCS最长公共子序列

最长公共子序列（longest common sequence）和最长公共子串（longest common substring）不是一回事儿。即一个给定的序列的子序列，就是将给定序列中零个或多个元素去掉之后得到的结果。什么是子串，给定串中任意个连续的字符组成的子序列称为该串的子串。

动态规划

设Ax,Bx表示 A 和 B的连续前 x 项构成的子序列，用LCS(x,y)表示它们的最长公共子序列长度，那原问题就是求LCS(m,n)。

用$L(x,y)$表示Ax和Bx的一个最长公共子序列。

  • 求LCS(x,y)的方法

(1) Ax = By那么A和B的最长公共子序列一定是这个元素

有 LCS(x,y) = LCs(x-1,y-1) + 1

(2)$Ax\neq By$

如果 $t\neq Ax$,则有$LCS(x,y)=LCS(x-1,y)$,因为与Ax 无关了

如果$t\neq By$，则$LCS(x,y)=LCS(x,y-1)$

$LCS(x,y)=LCS(x-1,y-1)+1 (Ax=By)$

$max(LCS(x-1,y),LCS(x,y-1)) (Ax\neq By)$

$0 如果 x=0 或者 y = 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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int f[N][N]; // f[i][j] 表示s1前i个字符和 s2前j个字符公共子序列的最大值
char s1[N], s2[N];
int main()
{
    int m,n;
    cin >> m >> n; // 字符串的长度
    cin >> s1+1 >> s2+1;
    f[1][0] = f[0][1] = 0;
    for(int i = 1;i <= m;i++)
    {
        for(int j = 1; j <= n;j++)
        {
            if(s1[i] == s2[j])  f[i][j] = f[i-1][j-1]+1;
            else f[i][j] = max(f[i-1][j],f[i][j-1]);
        }
    }
    cout << f[m][n];
    return 0;
}

L2-008 最长对称子串 （25 分)

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。

输入格式：
输入在一行中给出长度不超过1000的非空字符串。

输出格式：
在一行中输出最长对称子串的长度。

输入样例：
Is PAT&TAP symmetric?

输出样例：
11

原文链接：https://blog.csdn.net/weixin_43264529/article/details/88812551

暴力DP

设A[l][r]为字符串 str[l:r]的最长对称子串

对于第 l 位与第 r 位之间的字符串str[l:r]，如果其是对称子串的话，则满足str[l] == str[r]，且str[l+1: r-1]为对称子串

初始条件

A[i][j] == 1 - > 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
27
28
#include<isotream>
using namespace std;
vector<vector<int>> A(n,vector<int>(n,0));
int main()
{
    string str = "";
    getline(cin,str);
    int n = str.size();
    for(int i = 0;i < n;i++)
        A[i][i] = 1;
   	int Max = 1;
    for(int len = 1;len < n;len++) // 枚举子串长度
    {
        for(int l = 0;l + len< n;l++)
        {
            int r = l + len;
            if(str[l] == str[r])
            {
                if(A[l+1][r-1] == r - l -1)// 如果该区间的最长对称子串等于总长度
                {
                    A[l][r] = A[l+1][r-1] + 2;
                    if(A[l][r] > Max)
                        Max = A[l][r];
                }
            }
        }
    }    
}

最长连续和

题目描述：给出一个长度为n的序列A1，A2，…，An，求最大连续和。换句话说，要求找到1<=i<=j<=n，使得Ai+Ai+1+…Aj尽量大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
const int N = 110;

int a[N], d[N]; // d[i]表示以a[i]结尾的子段中的最大连续和
// 因为它没有限制长度(任意长度都行)，无非就是判断会不会有负数
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	d[1] = a[1];
	for (int i = 2; i <= n; i++) {
		if (d[i - 1] > 0)
			d[i] = d[i - 1] + a[i];
		else
			d[i] = a[i]; // 前面的都是负数，直接丢弃
	}
	cout << d[n];
	return 0;
}

examples

letcode 279.完全平方数

https://leetcode-cn.com/problems/perfect-squares/

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numSquares(int n) {
        // 如果是用动态规划来做，dp[i]表示的是i需要的最小的平方数字，动态转移的过程是，要么这个数字是来自于i - j*j这个数的和 + 1，要么是来自于它自己，取最小值
        vector<int> dp(n + 1);
        dp[0] = 0; 
        for(int i = 1; i <= n; i++){
            dp[i] = i; //dp[i]减小的可能性是包含某个平方数
            for(int j = 1; j <= sqrt(i); j++){
                dp[i] = min(dp[i], dp[i - j*j] + 1); //循环条件使得 i - j*j >=0
            }
        }
        return dp[n];
    }
};

azBNfs.md.jpg

解法二

遍历树的层数

d9b0IS.md.jpg

</a>

把 n 看成根节点， n 减去第一个可能的完全平方数的集合就是根的子节点。当某个节点的子节点的值第一次为 0 时，说明这一层我们已经找到了数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
class Solution {
public:
    int numSquares(int n) {
       // 定义一个队列，定义一个visited的list集合  
        queue<int> total;
        set<int> visited;
        int step = 0;
        total.push(n);
        while(!total.empty()){
            step++;
            int l = total.size(); // 记录每一层数的个数
            for(int i = 0; i < l; i++){
                // 这里是把每一层的循环完毕，所以是这一层的长度循环
                int top = total.front();
                total.pop(); //记录第一个值，然后删掉，
                //下一次第一个就是以前的第二个数据
                for(int j = 1; j <= sqrt(top); j++){
                    int x = top - j*j;
                    if(x == 0) return step;
                    if(visited.find(x) == visited.end() && x > 0){ //如果 x 不在visited中，存入visited
                        total.push(x); //存入x，
                        visited.insert(x);//避免重复
                    }
                }
            }
        }
        return n;
    }
};

数塔问题 (算法笔记p427)

采用递归求法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int f[10][10];
int n;
int dp[10][10];//有10 层数字
memset(a,-1,sizeof(dp));//初始化dp数组为-1
int F(int i,int j){
    if(dp[i][j]!=-1)
        return f[i][j];
    if(i==n)
        return f[i][j];
    dp[i][j]=max(F(i+1,j),F(i+1,j+1))+f[i][j];
    return dp[i][j];
}
int main(){
    cin>>n;
    for(int i = 1;i<=n;++i){
        for(int j = 1;j<=i;j++)
        {
            cin>>f[i][j];//输入塔的数字
	}
    }
    cout<<F(1,1);
    return 0;
}

自底向上递推写法

1
2
3
4
5
6
7
8
for(int j=1;j<=n;j++){
    dp[n][j] = f[n][j];//n表示层数
}
for(int i = n-1;i>=1;i--){
    for(int j=1;j<=i;j++){
        dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + f[i][j];
    }
}