第三步两个区间 DP

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

最长回文子序列已给出，补全石子合并（按区间长度从短到长填），输出「石子 4、1、2、3 的最小代价/bbbab 的回文长度」。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 第二步压掉一维第四步三个二维 DP →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using Item = pair<int, int>;   // (重量, 价值)

const vector<Item> ITEMS = {{3, 8}, {4, 9}, {5, 11}};

long long merge_cost(const vector<int>& a) {
    int n = a.size();
    const long long INF = 1000000000000000000LL;
    vector<long long> pre(n + 1, 0);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    // TODO: 外层区间长度 L 从 2 到 n；内层左端点 i，右端点 j = i + L - 1
    // TODO: dp[i][j] 先设 INF，再枚举断点 k，取 dp[i][k] + dp[k+1][j] + 区间和 的最小值
    (void)INF;
    return dp[0][n - 1];
}

int lps(const string& s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
            else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    return dp[0][n - 1];
}

int main() {
    cout << merge_cost({4, 1, 2, 3}) << "/" << lps("bbbab") << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

第三步两个区间 DP

更多题目

全部评论