C++ 两种简洁的解法：记忆化搜索 and 区间DP

记忆化搜索

思路

• 考虑一下，当前操作有三个状态量：当前左端点、当前右端点、当前操作次数
• 实际上，确定了当前左端点的位置和当前操作次数后，当前右端点就唯一确定了
• 定义dfs(l, step): 从左端点为l, 第step次操作开始搜索得到的最大分数。用f[l][step]记录答案。
• 从dfs(0,0)开始搜就完了

代码

typedef long long ll;
class Solution {
public:
    int f[1010][1010];
    ll dfs(int l, int step, vector<int>& w, vector<int>& c){ // dfs(l, step) 代表从左端点为l, 第step次操作开始搜索得到的最大分数
        int &x = f[l][step];
        if(step == c.size()) return 0;
        if(x != -1) return x;

        int r = w.size() - step + l - 1; // 右端点
        ll ans = max(dfs(l+1, step+1,w,c)+w[l]*c[step], 
            dfs(l, step+1,w,c)+w[r]*c[step]);
        return x = ans;
    }
    int maximumScore(vector<int>& w, vector<int>& c) {

        memset(f, -1, sizeof f);
        return dfs(0,0,w,c);

    }
};

区间DP

思路

• 定义f[i][j]为区间[i,j]能获得的最大分数
• 因为n的范围远大于m，当n>2m时，要删去中间用不到的数
• 枚举区间长度len和左端点i，计算右端点j，则状态转移方程f[i][j] = max(f[i+1][j] + w[i] *c[n-len], f[i][j-1]+w[j] * c[n-len]

代码

class Solution {
public:
    int maximumScore(vector<int>& w, vector<int>& c) {
        int n = w.size(), m = c.size();
        if(n > 2 * m){ // 预处理, 删掉数组中段没有用的部分
            int x = m, y = n - m;
            while(y < n) w[x ++] = w[y ++];
            n = x;
        }

        vector<vector<int>> f(n+6, vector<int>(n+6));
        for(int len = n - m + 1; len <= n; len ++){ // 用边界值考虑len的枚举起点: n = m
            for(int i = 1; i+len-1 <= n; i ++){ // 要用到f[i][j-1], 防止越界，i从1开始枚举
                int j = i + len - 1;
                f[i][j] = max(f[i+1][j] + w[i-1]*c[n-len], // w[i-1]是因为i从1开始枚举
                    f[i][j-1] + w[j-1]*c[n-len]);
            }
        }
        return f[1][n];
    }
};