最佳观光组合——动态规划

最佳观光组合

题目来源 :leetcode第1014题

在看题目解析之前,我一直在推公式,然而得到的公式却没什么鬼用,可能我太蠢了,dp问题也太tm难了,呜呜呜呜呜。


问题描述

言归正传,贴上题目。

最佳观光组合——动态规划


思路

  1. 题目要求 \(values[i] + values[j] + i - j\) ,因为 \(i < j\) ,所以当我们要选 \(j\) 间房子是,我们要在前面 \([0,j - 1]\) 之间选个房子 \(i\)。
  2. 所以公式可以分成 \(values[i] + i\) 和 \(values[j] - j\) ,当我们要选 \(j\) 号房子是,因为 \(values[j] - j\) 项是一个固定值,所以我们就要在前面 \([0,j - 1]\) 间寻找一个最优解.由最值定理可知当 \(values[i] + i\) 是 \([0,j - 1]\) 的最优解时,则 \(i\) 就是 \([0 , i - 1]\) 后的最优解。所以利用动态规划来解决此问题。
  3. 设 \(dp[i]\) 为 \([0 , i]\) 的 \(values[i] + i\) 最优解,所以状态转移方程为:

\[dp[i] = max(dp[i - 1] , values[i] + i) \]

  1. 最后利用一个变量来记录当前 \(values[i] + values[j] + i - j\) 的最大值即可。
  2. 代码中状态转移方程是:

\[dp[i] = max(dp[i - 1] , values[i - 1] + i - 1) \]

\(values[i - 1] + i - 1\) 的原因是因为,\(dp[i]\) 中 \(i\) 的定义域是 \(from 1 to n\) 的,所以对应的 \(values[i]\) 的定义域想要对应上,则要 \(i - 1\) 。

c++ 代码

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int n = values.size();
        int ans = 0;
        vector<int> dp(n + 1,0); // dp[0]设为0,dp[0]的意思就是只有0号房子,因为题目要求选两间房子,所以dp[0]就为0。
        for(int i = 1;i <= n;i++){
            dp[i] = max(dp[i - 1] , values[i - 1] + i - 1);
            ans = max(ans,(dp[i - 1] + values[i - 1] - (i - 1)));
        }
        return ans;
    }
};

代码优化

因为状态转移方程只与 \(i\) 和 \(i - 1\) 有关,所以可以利用滚动数组来减少内存消耗。

上一篇:贪心算法(背包问题)


下一篇:Java程序员的春天!java测试岗位面试题