线性dp题型总结

缺乏、安全感 2022-03-01 02:52 194阅读 0赞

## LIS问题 最长上升子序列 ##

### [poj-Longest Ordered Subsequence][] ###

### 状态方程 ###

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    #include <iostream>
    using namespace std;
    int l; //序列的长度
    vector<int> vec;
    vector<int> dp;
    int main()
    { 
        cin >> l;
        vec.resize(l + 1);
        dp.assign(l + 5, 0);
        int ans;
        for (int i = 1; i <= l; i++) //元素下标从1开始
        { 
            cin >> vec[i];
        }
        for (int i = 1; i <= l; i++)
        { 
            ans = 0;
            for (int j = 0; j < i; j++)
            { 
                if (vec[j] < vec[i])
                { 
                    ans = max(ans, dp[j]);
                }
            }
            dp[i] = ans + 1;
        }
        int maxn = dp[0];
        for (int i = 0; i <= l; i++) //最后一定要遍历一遍dp数组，因为最长的不一定是dp最后一个元素
        { 
            maxn = max(dp[i], maxn);
        }
        cout << maxn << endl;
        return 0;
    }

### LCS问题 最长公共子序列 ###

### [poj-1458.Common Subsequence][] ###

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int len = 205;
    char s1[len], s2[len];
    int dp[len][len] = { 0};
    int main()
    { 
        while (scanf("%s%s", s1 + 1, s2 + 1) == 2) //字符串下表从1开始
        { 
            memset(dp, 0, sizeof(dp));
            int l1 = strlen(s1 + 1);
            int l2 = strlen(s2 + 1);
            for (int i = 1; i <= l1; i++)
            { 
                for (int j = 1; j <= l2; j++)
                { 
                    if (s1[i] == s2[j])
                    { 
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                    else
                    { 
                        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            printf("%d\n", dp[l1][l2]);
        }
        return 0;
    }

### 01背包问题 ###

### [poj-3624.Charm Bracelet][] ###

dp\[i\]\[j\]表示第i个物品装入容积为j的背包中，但是当dp\[i\]\[j\]被求出后，dp\[i-1\]\[j\]的值对求任何dp\[i\]\[k\]\[k<j\]都没有用了，所以这么定义数组，会浪费很大空间，因此可以设成滚动数组，dp\[j\]表示容积为j的背包中物品的价值。  
dp\[j\] = max(dp\[j\], dp\[j - items\[i\].w\] + items\[i\].d)： 前部分dp\[j\]表示不放入第i件物品，dp\[j - items\[i\].w\] + items\[i\].d表示放入第i减物品，所以背包容积要减小。

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    #include <iostream>
    using namespace std;
    struct Item
    { 
        int w, d; //w表示物品的体积，d表示物品的价值
    };
    Item items[3500];
    int dp[13000];
    int main()
    { 
        int N, M;
        cin >> N >> M; //n种物品，m的容积
        for (int i = 1; i <= N; i++)
        { 
            cin >> items[i].w >> items[i].d;
        }
        for (int i = 0; i <= M; ++i)
        { 
            if (items[1].w <= i)
                dp[i] = items[1].d;
            else
                dp[i] = 0;
        }
        for (int i = 2; i <= N; i++)
        { 
            for (int j = M; j >= 0; --j)
            { 
                if (items[i].w <= j)
                    dp[j] = max(dp[j], dp[j - items[i].w] + items[i].d);
            }
        }
        cout << dp[M] << endl;
        return 0;
    }

[poj-Longest Ordered Subsequence]: http://poj.org/problem?id=2533
[poj-1458.Common Subsequence]: http://poj.org/problem?id=1458
[poj-3624.Charm Bracelet]: http://poj.org/problem?id=3624