线性动态规划

三角形数字

f[i][j]表示从开始的位置到i，j位置的路径之和的最大值。
因为f[i][j]是要求的那个，所以我们要求出它的状态方程
f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j])
ok，现在开始我们做这道题

#include 
#include 
#include 
#include 
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {vector<vector<int>> a(n+1,vector<int>(n+1));
    vector<vector<int>> f(n+1,vector<int>(n+1,INT_MIN));//初始为最小值
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>a[i][j];
        }
    }
    f[1][1]=a[1][1];//第一个数据是确定的
    for(int i=2;i<=n;++i)
    {
        for(int j=1;j<=i;++j)
        {
            f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
        }
    }
    int ret=INT_MIN;
    for(int i=1;i<=n;++i)
    {
            if(f[n][i]>ret)
                ret=f[n][i];
    }
    cout<<ret<<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

优化：

#include 
#include 
#include 
using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<vector<int>> a(n+1,vector<int>(n+1));
    vector<int> f(n+1,-1000);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>a[i][j];
        }
    }
    f[1]=a[1][1];
    for(int i=2;i<=n;i++)
    {
        for(int j=i;j>=1;--j)//从后往前不会被覆盖
        {
            f[j]=max(f[j-1]+a[i][j],f[j]+a[i][j]);
        }
    }
    int ret=-1000;
    for(int i=1;i<=n;++i)//找出最大
        ret=max(ret,f[i]);
    cout<<ret<<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

最长上升子序列1

题目描述：从一段数据中选择最长的子序列，子序列是非递减的。求的是这个子序列的长度的最大值。

问题解决：f[i]表示以第i个数结尾的子序列的最大值。
方程计算：f[i]=max(f[i-1],f[i-2],f[i-3]…f[i-k]…f[0])+1当然也可以在每个里面加1,注意：a[i-k]的值必须满足子序列的条件。

#include 
#include 
using namespace std;

int main() 
{
    int n;
    cin>>n;
    vector<int> v(n),f(n,1),g(n);
    for(int i=0;i<n;i++) cin>>v[i];

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(v[j]<v[i])
            {
                f[i]=max(f[i],f[j]+1);         
            }
        }
    }
    int ret=0;
    for(int i=0;i<n;i++)
    {
        if(f[i]>ret)
        ret=f[i];
    }
    cout<<ret<<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

如何获得最大子序列呢？
我们用g数组保存最大数组开始转换的下标，

#include 
#include 
using namespace std;

int main() 
{
    int n;
    cin>>n;
    vector<int> v(n),f(n,1),g(n);
    for(int i=0;i<n;i++) cin>>v[i];

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(v[j]<v[i])
            {
                if(f[i]<f[j]+1)//记录子序列转换的位置
                g[i]=j;
                f[i]=max(f[i],f[j]+1);

            }
        }
    }
    int ret=0,k=0;
    for(int i=0;i<n;i++)
    {
        if(f[i]>ret)
        {
            ret=f[i];
            k=i;  
        }
    }

    for(int i=0;i<ret;i++)
    {
        cout<<v[k]<<' ';
        k=g[k];//依次还原
    }
    cout<<endl;
    cout<<ret<<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
39
40
41
42
43

最长公共子序列

问题描述：有两个字符串，选出它们公共的子串，并且该子串的长度最大。

问题解决：f[i][j]表示字符串1(str1)以i结尾，字符串2(str2)以j结尾的最大子串。
我们知道动态规划类题目都会用到上一次的结果，那么f[i][j]怎么用上一层计算的结果来计算呢?
f[i][j]有这么几种分法：str1[i]==str2[j],那么f[i][j]=f[i-1][j-1]+1
str1[i]!=str2[j],这里就有3种情况：
1.i-1之前的子串与j之前的匹配
2.j-1之前的子串与i之前的子串匹配
3.i-1，j-1之前的子串匹配。
其中1，2两种情况包含了第3种情况。
f[i][j]=max(f[i-1][j],f[i][j-1])
最后还需要把这两个绿的地方进行比较一下。因为有i-1的情况，所以都从1位置开始读入，开始匹配。

#include 
#include 
#include 
using namespace std;

int main()
{
    string str1,str2;
    while( cin>>str1>>str2)
    {
        str1.insert(str1.begin(), ' ');
        str2.insert(str2.begin(), ' ');
    vector<vector<int>> f(str1.size(),vector<int>(str2.size(),0));
    for(int i=1;i<str1.size();++i)
    {
        for(int j=1;j<str2.size();++j)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(str1[i]==str2[j])
                f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }

    }
    
    cout<<f[str1.size()-1][str2.size()-1]<<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