【动态规划】Leetcode 1014. 最佳观光组合

题目信息

解题思路

看到这题的时候，最想到的是把所有节点的最高得分计算出来，我们来看一下最高得分会是什么样子的。

首先我们来分析一下，这个题目都有什么状态出现。

1. 当数组就包含两个元素的时候，返回结果肯定是这两个景点的得分。
   
2. 当增加到n个景点时候，我们可以考虑把所有的景点跟这个景点之前的最高得分计算出来
   

关于第二种情况，使用双层循遍历暴力解决问题，从这数据量上来看，结果会超时的，哈哈哈……这个行不通的

那么就要考虑其他解法，例如动态规划，这时候考虑一下这题的状态方程是什么样子的。

得分的计算公式为：values[i] + values[j] + i - j，并且i < j

第一种情况，首先计算出两个景点的最优解，这个很简单，可以直接计算：values[1] + values[0] - 1

然后就是n个景点的计算，首先算一下i位置上的得分计算方式，假设x是[0, i-1)中能和i-1位置计算得到最高分的值，得分记作values[i-1] + values[x] + i -j

那么此时，计算i位置上的得分时，我们已经知道[0, i-1)中的最合适的值，我们可以得到这段距离里面的能和i计算最优解的位置是x，但是我们需要判断一下，x和i-1这两个景点，哪个能得到的分数最高，作为包含i景点时的最高得分。

当所有景点的得分都算出来的时候，我们判断哪个景点上的得分最高，那个就是一对观光点能取得的最高分。

代码

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        // 获取数组的长度
        int n = values.length;
        // 当数组只有两个元素的时候，获得评分
        int ans = values[1] + values[0] - 1;
        // 记录包含第 i 位观光点时的评分
        int index = ans;
        // 从第三个观光点开始计算
        for (int i = 2; i < n; i++) {
            // 当包含第三个观光点时，评分最大值
            index = Math.max(index + values[i] - values[i - 1] - 1, values[i] + values[i - 1] - 1);
            // 直到第 i 位时，所有评分中的最高评分，最高分可能包含当前节点，也可能不包含
            ans = Math.max(ans, index);
        }
        // 返回结果
        return ans;
    }
}

结果