牛客 QQ10 石子合并

概述

https://www.nowcoder.com/practice/3eef8d66b0fa4f71a8498974547fe670

动态规划法

求最优，第一时间想到动态规划法，但是这里的状态要怎么定义好嘞。

其实和 LeetCode 上一道戳气球的题很像，状态定义为开区间 i，j 内的最大得分。

实现的时候 dp 数组设置小了，导致越界，没报错。 LeetCode 中之所以会报错是因为它额外用了一个程序来检测错误，看来我们不能依赖这一点呀。

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> nums;
vector<int> sums;
vector<vector<int>> dp;

int sumlr(int l, int r) {
    if (l == 0) return sums[r];
    else return sums[r] - sums[l-1];
}

int helper(int l, int r) {
    if (r - l == 3) return nums[l+1] * nums[r-1];
    if (r - l < 3) return 0;
    if (dp[l+1][r] != -1) return dp[l+1][r];
    int res = 0;
    for (int i = l + 1; i <= r - 2; i ++) {
        res = max(res, helper(l, i+1) + helper(i, r) + sumlr(l+1, i) * sumlr(i+1, r-1));
    }
    dp[l+1][r] = res;
    return res;
}

int main() {
    cin >> n;
    nums.resize(n);
    sums.resize(n);
    dp.resize(n + 1, vector<int>(n + 1, -1));
    for (int i = 0; i < n; i ++) {
        cin >> nums[i];
        if (i != 0) {
            sums[i] = sums[i-1] + nums[i];
        } else {
            sums[i] = nums[i];
        }
    }
    cout << helper(-1, n);
}

Links: 牛客-qq10-石子合并

未经允许，禁止转载，本文源站链接：https://iamazing.cn/