动态规划处理序列两边的技巧

今天leetcode比赛的第三题是一个序列两边取值求最大值的问题，这个问题看起来比较典型，因此单独讨论一下这个题目。

题目是这样的：

给你两个数组 nums 和 multipliers，其中nums的长度为n，multipliers的长度为m。

你需要执行恰好 m 步操作。在第 i 步操作（从 1 开始 计数）中，选择数组 nums 开头处或者末尾处 的整数 x ，获得 multipliers[i] * x 分，并累加到你的分数中。每次执行后将 x 从数组 nums 中移除。

在执行 m 步操作后，返回 最大 分数。

比如输入：nums = [1,2,3], multipliers = [3,2,1]

则最大值方案如下：

• 选择末尾处的整数 3 ，[1,2,3] ，得 3 * 3 = 9 分，累加到分数中。
• 选择末尾处的整数 2 ，[1,2] ，得 2 * 2 = 4 分，累加到分数中。
• 选择末尾处的整数 1 ，[1] ，得 1 * 1 = 1 分，累加到分数中。
• 总分数为 9 + 4 + 1 = 14 。

解题思路

这个题目看了下排名第一的大大用的是DFS搜索，也没有做剪枝和缓存，语言是python，竟然没有超时，这种解法是比较容易想到的，每次往左和往右2个分支算出结果，取较大值。

搜索算法比较耗时，复杂度高，每一次都是2个分支，也就是

。不过leetcode对Python貌似相当宽容，这么高的复杂度也能运行通过，看来如果想拿名次的童鞋可以优先考虑Python，能够快速过题。

来看下Python和C++的对比：

懂了吧，我用C++也写了个搜索的但是提示超时。没办法，只能DP撸起。

这道题比较典型就在于需要往左右2边取值，同时往左右两边操作序列不好定义状态转移方程。

对于m步，我们可以想到每一步的集合，比如第一步我们只可能左边取一个数或者右边取一个数字，我们定义f[i][j]表示左边取i个数右边取j个数，那么i+j肯定等于m。

注意f[i][j]这个映射关系中，f[i][j] = max(f[i-1][j]+value1, f[i][j-1]+value2)

由于是递推关系，我们可以求得第m步中，所有的f[i][j]值，选择一个最大值输出。这样只需要两次循环就可以解决问题。

这里的技巧是定义i和j为左右两边的取值数量，这样能够比较方便的进行递推处理。比较有意思的是第一层循环迭代值是k，而i和j的关系是i+j=k，不是直接使用k这个值。

如果遇到类似的两边取序列问题可以参考这种做法。

DP的复杂度是

，比搜索快很多。

解题源码：

class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& mu) {
        int n = nums.size();
        int m = mu.size();
        int f[1010][1010];
        f[0][0] = 0;
        int res = INT_MIN;

        for(int k=1; k<=m; k++){
            for(int i=0; i<=k; i++){
                int j = k-i;
                f[i][j] = INT_MIN;
                if(i>0){
                    //左边取值的情况
                    int t = f[i-1][j] + nums[i-1]*mu[k-1];
                    f[i][j] = max(t, f[i][j]);
                }
                if(j>0){
                    //右边取值的情况
                    int t = f[i][j-1] + nums[n-j]*mu[k-1];
                    f[i][j] = max(t, f[i][j]);
                }
                if(k==m){
                    res = max(res, f[i][j]);
                }
            }
        }

        return res;
    }
};

代码细节：

res和f[i][j]初始为INT_MIN，有可能出现负数，f[0][0]取值为0，表示什么都不取。

左边取值的情况下，nums[i-1]使用i-1而不是i，是因为i为1的话表示取左边第一个数，所以要减1。

动态规划大部分都是中等题和难题，如果还有不懂的就留言吧。

彩蛋

能看到这里的都是爱学习的娃，那么再看点不一样的~最近dansen在Github上创建了一个算法的开源项目，主要是整理leetcode算法学习路线的（可以整理任意平台的学习路线），我打算把上篇文章说的路线规划和题解、算法资料全部放到Github上面，有兴趣的童鞋可以加我一起整理资料，争取让这个不一样的开源项目早日为大家所用。提前给你们看个图：