LeetCode 1014 Best Sightseeing Pair DP

You are given an integer array values where values[i] represents the value of the ith sightseeing spot. Two sightseeing spots i and j have a distance j - i between them.

The score of a pair (i < j) of sightseeing spots is values[i] + values[j] + i - j: the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

Solution

设 \(dp[j]\) 表示以 \(j\) 结尾的答案，转移方程：

\[dp[j] = \max_i(v[i]+v[j]+i-j)=v[j]-j+\max_i(v[i]+i) \]

因此只需要维护每个位置结尾的 \(\max_i(v[i]+i)\)

点击查看代码 
class Solution {
private:
    int dp[50004];
    int MAX = -1;
    int add[50004];
public:
    int maxScoreSightseeingPair(vector& values) {
        int n = values.size();
        if(n==2){return values[0]+values[1]-1;}
        for(int i=0;i
DPLeetCode算法

相关

#leetcode404.所有左叶子节点之和

#leetcode437.路径总和II

#leetcode203

#leetcode167

#leetcode26

标签