动态规划经典问题再入门¶

前置知识¶

动态规划经典问题入门

目标¶

经典问题，递归实现，循环迭代实现，打印方案积累代码经验

最长上升子序列问题¶

递归实现, 以子序列长度作为参数设计函数¶

// TLE

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int a[N], n;
int k[N], ret;                          // 用一个k[N]来存下标，不是直接存具体数值 B[k[N]]
                    // 而是存有关联的信息，下标
                    // 这是常见的“简化”

void dfs(int len){                         // 传递的参数len，是最长子序列的长度
    if (len > ret) ret = len;              

    for (int i = k[len] + 1; i <= n; i++)  // 枚举下一个位置是谁
        if (a[i] > a[k[len]]){             // 满足更长一点的条件，就加上
            k[len + 1] = i;
            dfs(len + 1);
        }
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    k[0] = 0, a[0] = -2e9;
    dfs(0);

    cout << ret << '\n';

    return 0;
}

// 这个搜索，和我们平时的dfs的编写，有些不同
// 平时的dfs，框架是问题的边界，求解子问题
// 这个函数，并没有显性的写出来边界，但是在for循环的时候，如果到了最后一个数，就不会进入for循环
// 也就实现了终止钻下去的过程

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int a[N], n;
int ret;                      // 我们发现这个K[]数组是多余，因为每次只用最后一个数
                      // 那么，这最后一个数，就作为函数参数吧

void dfs(int len, int tail){
    if (len > ret) ret = len;

    for (int i = tail + 1; i <= n; i++)
        if (a[i] > a[tail]){
            dfs(len + 1, i);
        }
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    a[0] = -2e9;
    dfs(0, 0);

    cout << ret << '\n';

    return 0;
}

递归实现, 子集枚举, 选或者不选¶

int numList[] = {5, 2, 7, 3, 4, 6}; 
// solution is finally set of 0s and 1s..pick or leave.
//               0  1  0  1  1  1

int m = 6;

// called with LIS(0, m)
int LIS(int i, int prev)
{
    if(i == m)
        return 0;

    int choice1 = LIS(i+1, prev);                // LEAVE
    int choice2 = 0;

    if(prev == m || numList[prev] <= numList[i])
        choice2 = LIS(i+1, i) + 1;

    return max(choice1, choice2);
}


LIS(0, m);  // 需要分析一下，为甚调用的时候prev，传的是m
            // 传-1行不行

循环实现, 刷表法, 填表法¶

// 刷表法
#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int a[N], n;
int dp[N], ret;

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 刷表法
    a[0] = -2e9, dp[0] = 0;
    for (int i = 0; i < n; i++)                 // 枚举以i为结尾
        for (int j = i + 1; j <= n; j++)    // 枚举下一个数
            if (a[j] > a[i]) dp[j] = max(dp[j], dp[i] + 1); 

    for (int i = 1; i <= n; i++) ret = max(ret, dp[i]);
    cout << ret << '\n';

    return 0;
}

// 填表法
#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int a[N], n;
int dp[N], ret;

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 填表法
    a[0] = -2e9, dp[0] = 0;
    for (int i = 1; i <= n; i++)                 // 枚举以i为结尾
        for (int j = 0; j < i; j++)          // 枚举从哪个数来
            if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1); 

    for (int i = 1; i <= n; i++) ret = max(ret, dp[i]);
    cout << ret << '\n';

    return 0;
}

// 刷表法，更符合人的正常思考
// 常用的填表法，当前状态，从哪些状态转移过来
// 逆向思维，而已

打印方案¶

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int a[N], n;
int dp[N], ret, tail;
int pre[N];                 // 记录方案的核心要点是：记录决策

void print(int u){
    if (u == 0) return ;

    print(pre[u]);
    printf("%d ", a[u]);
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 填表法
    a[0] = -2e9, dp[0] = 0;
    for (int i = 1; i <= n; i++)             // 枚举以i为结尾
        for (int j = 0; j < i; j++)      // 枚举从哪个数来
            if (a[j] < a[i]){
                if (dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                    pre[i] = j;
                }
            }

    for (int i = 1; i <= n; i++){
        if (ret < dp[i]) ret = dp[i], tail = i;
    }
    cout << ret << '\n';
    print(tail);                    // 找到LIS的最后一个字符，然后开始递归打印方案
    puts("");

    return 0;
}

最长公共子序列问题¶

递归实现¶

string str1 = "abcdefgzh";
string str2 = "ackghefhlmn";

// abcdefgzh
// 101011001

// ackghefhlmn
// 11000111000

// acefh

// called with LCS(0, 0)
int LCS(int i, int j)
{
    if(i == sz(str1) || j == sz(str2))
        return 0;

    if(str1[i] == str2[j])
        return 1 + LCS(i+1, j+1);

    int choice1 = LCS(i+1, j);
    int choice2 = LCS(i, j+1);

    return max(choice1, choice2);
}

循环实现, O(n^4)¶

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

char A[N], B[N];
int n, m, dp[N][N]; // dp[i][j]表示以A[i] B[j]作为结尾的两个子串，最长公共子序列的长度

int main(){
    cin >> n >> m;
    scanf("%s%s", A + 1, B + 1);

    // 这种枚举方式，是知道具体公共的位置，O(n^4) ，超时
    // 同时，我们也并不需要知道具体是哪个位置公共的
    for (int i = 0; i < n; i++)          // 枚举A取到了i位置, B取到了j位置
        for (int j = 0; j < m; j++){     
            if (A[i] != B[j]) continue;  // 当A[i] == B[j]，就符合公共条件，可以看下一个位置

            for (int ni = i + 1; ni <= n; ni++)  // 两重循环枚举下一个可能位置是什么
                for (int nj = j + 1; nj <= m; nj++)
                    if (A[ni] == B[nj]) dp[ni][nj] = max(dp[ni][nj], dp[i][j] + 1);
        }

    int ret = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ret = max(ret, dp[i][j]);

    cout << ret << '\n';

    return 0;
}

循环实现, O(n^2)¶

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

char A[N], B[N];
int n, m, dp[N][N]; // dp[i][j]表示以A[i] B[j]作为结尾的两个子串，最长公共子序列的长度

int main(){
    cin >> n >> m;
    scanf("%s%s", A + 1, B + 1);

    for (int i = 1; i <= n; i++) dp[i][0] = 0;  // B串0个字符，公共长度就是0
    for (int j = 1; j <= m; j++) dp[0][j] = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            // dp[i-1][j] 以A[i-1] B[j]为结尾的两个子串，最长公共子序列长度
            // dp[i][j-1] 以A[i] B[j-1]为结尾的两个子串，最长公共子序列长度
                        // 并不需要子序列的结尾就是i，或者就是j
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); 
            if (A[i] == B[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
        }

    cout << dp[n][m] << '\n';

    return 0;
}

打印方案¶

// 打印方案

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

char A[N], B[N];
int n, m, dp[N][N]; // dp[i][j]表示以A[i] B[j]作为结尾的两个子串，最长公共子序列的长度
int pre[N][N];      // 核心：记录如何转移的, 记决策

void print(int i, int j){
    if (i == 0 || j == 0) return ;

    if (pre[i][j] == 3){
        print(i - 1, j - 1);
        printf("%c", A[i]);
    }
    else if (pre[i][j] == 1) print(i - 1, j);
    else if (pre[i][j] == 2) print(i, j - 1);
}

int main(){
    cin >> n >> m;
    scanf("%s%s", A + 1, B + 1);

    for (int i = 1; i <= n; i++) dp[i][0] = 0;  // B串0个字符，公共长度就是0
    for (int j = 1; j <= m; j++) dp[0][j] = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            if (dp[i - 1][j] > dp[i][j - 1]){
                dp[i][j] = dp[i - 1][j];
                pre[i][j] = 1;
            }
            else{
                dp[i][j] = dp[i][j - 1];
                pre[i][j] = 2;
            }

            if (A[i] == B[j]){
                if (dp[i - 1][j - 1] + 1 > dp[i][j]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    pre[i][j] = 3;
                }
            } 
        }

    cout << dp[n][m] << '\n';
    print(n, m);
    puts("");

    return 0;
}

数字三角形问题¶

递归实现, TLE¶

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int a[N][N], dp[N][N], f[N][N];
int n;

int solve(int x, int y)
{
    // 问题的边界
    if (x == n) return a[x][y];

    // 求解子问题
    int u = solve(x + 1, y);
    int v = solve(x + 1, y + 1);

    if (u > v) return a[x][y] + u;
    else return a[x][y] + v;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];
    }

    cout << solve(1, 1) << '\n';

    return 0;
}

递归实现, 记忆化¶

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int mem[N][N];
int a[N][N], dp[N][N], f[N][N];
int n;

int solve(int x, int y)
{
    //问题的边界
    if (x == n) return a[x][y];

    int &ret = mem[x][y];
    if (ret != -1) return ret;

    //求解子问题
    int u = solve(x + 1, y);
    int v = solve(x + 1, y + 1);

    if (u > v) return ret = a[x][y] + u;
    else return ret = a[x][y] + v;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];
    }

    //递归+记忆化
    memset(mem, -1, sizeof mem);
    cout << solve(1, 1) << '\n';

    return 0;
}

循环实现, 从上往下¶

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int mem[N][N];
int a[N][N], dp[N][N], f[N][N];
int n;

void recur01()
{
    dp[1][1] = a[1][1];
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];

    int maxn = -2e9;
    for (int j = 1; j <= n; j++)
        maxn = max(maxn, dp[n][j]);

    cout << maxn << '\n';
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];
    }

    recur01();

    return 0;
}

循环实现, 从下往上¶

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int mem[N][N];
int a[N][N], dp[N][N], f[N][N];
int n;

void recur02()
{
    for (int j = 1; j <= n; j++) f[n][j] = a[n][j];

    for (int i = n - 1; i >= 1; i--)
        for (int j = i; j >= 1; j--){
            f[i][j] = a[i][j] + max(f[i+1][j], f[i+1][j+1]);
        }

    cout << f[1][1] << '\n';
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];
    }

    recur02();

    return 0;
}

总结¶

经典问题，常看常新，多加回顾总结

动态规划 经典问题再入门¶

前置知识¶

目标¶

最长上升子序列问题¶

递归实现, 以子序列长度作为参数设计函数¶

递归实现, 子集枚举, 选或者不选¶

循环实现, 刷表法, 填表法¶

打印方案¶

最长公共子序列问题¶

递归实现¶

循环实现, O(n^4)¶

循环实现, O(n^2)¶

打印方案¶

数字三角形问题¶

递归实现, TLE¶

递归实现, 记忆化¶

循环实现, 从上往下¶

循环实现, 从下往上¶

总结¶

动态规划经典问题再入门¶