程序地带

LeetCode : 1014. 最佳观光组合


题目描述:


解题思路:

看到这个题目,啪的一下很快啊就想到了动态规划,并写出了转移方程式:


// dp[i][j] 代表数组[i,j]范围内最高分
dp[i][j] = Max(dp[i][j-1], dp[i+1][j], A[i] + A[j] + i - j)

代码如下:


class Solution {
public int maxScoreSightseeingPair(int[] A) {
int len = A.length;
int[][] dp = new int[len][len];
for(int i = 1;i < len;i++) {
dp[i-1][i] = A[i] + A[i-1] - 1;
}
for(int i = 2;i < len;i++) {
for(int j = 0;j < len - i;j++) {
dp[j][j + i] = Math.max(A[j] + A[j + i] - i, Math.max(dp[j][j + i - 1],dp[j+1][j+i]));
}
}
return dp[0][len - 1];
}
}

结果就超出内存限制了,我大意了啊,一维dp就可以,修改一下代码:


class Solution {
public int maxScoreSightseeingPair(int[] A) {
int len = A.length;
if(len <= 0) {
return 0;
}
int[] dp = new int[len];
for(int i = 1;i < len;i++) {
dp[i] = A[i] + A[i-1] - 1;
}
for(int i = 2;i < len;i++) {
for(int j = len - 1;j >= i;j--) {
dp[j] = Math.max(Math.max(dp[j], dp[j-1]), A[j] + A[j - i] - i);
}
}
return dp[len - 1];
}
}

结果就超出时间限制,可恶,连动态规划都不行了吗?看样子要求O(N),也就是一次扫描。当到 j 时,怎么求[0,j]的最高分?一种情况是[0,j-1]的最高分,另一种情况A[j]与之前某个位置组成最高分,计算公式A[i] + A[j] + i - j,A[j] - j 不变,也就是与之前A[i] + i 最高的情况组成最高分,我又啪的一下想到动态规划,而且发现只与之前的结果比较,之前结果可用变量记录,所以dp的含义变了:


// dp[i] 代表[0,i] 范围内 A[k] + k 的最大值
dp[i] = Math(dp[i-1], A[i] + i)

最后代码:


class Solution {
public int maxScoreSightseeingPair(int[] A) {
int len = A.length;
int res = 0;
int[] dp = new int[len];
dp[0] = A[0];
for(int i = 1;i < len;i++) {
res = Math.max(res, dp[i-1] + A[i] - i);
dp[i] = Math.max(dp[i-1], A[i] + i);
}
return res;
}
}

 


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Yang_RT/article/details/112689395

随机推荐

SSH连接VMware显示port 22:connection failed

SSH连接VMware显示port22:connectionfailed查找了很多解决方案,都不能解决……不过大家确实都遇到过很多类似的问题,例如这里。按照这里的方案做了之...

DeadPool loves Star 阅读(590)

哈夫曼编码

7-7哈夫曼编码(30分)给定一段文字,如果我们统计出字母出现的频率,是可以根据哈夫曼算法给出一套编码,使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼...

weixin_47750287 阅读(357)