Algorithm
https://leetcode-cn.com/problems/best-sightseeing-pair/
class Solution:
# 这里遍历超时了
def maxScoreSightseeingPair(self, A: List[int]) -> int:
l = len(A)
s = [0]*l
for i in range(l):
for j in range(i+1,l):
s[i] = max(A[i]+A[j]+i-j,s[i])
return max(s)
# dp
def maxScoreSightseeingPair1(self, A: List[int]) -> int:
pre = now = 0
for i in A:
# now 指当前的最优解
now = max(now,pre+i)
# pre 指的是前面所有景点评分中的最大值,到下一个遍历时 -1
pre = max(pre,i) -1
return now
到当前景点为止的最优解 = max(当前景点前的最优解, 当前景点前最大景点评分相对于当前节点的评分+ 当前景点评分)
f (nums[i]) = max( f(nums[:i]) , g(nums[:i-1]) + i)
# f 当前最优解
f(i) = max(f(i-1),g(i-1)+i)
# g i轮前的最大值,相对于i轮的评分
g(i) = max(g(i-1),i) - 1
说起来比较绕,emmmmmm。dp就是这样,没办法唉🐶(或者我还没想好怎么表述,先这样吧)
Review
X-Y问题,这个现象非常有意思。我们可能经常遇到过,但是没有给它一个名字,所以没能认识到它们其实是一类问题,因此走了很多弯路。
- 有人想做 X。
- 但是他不知道怎么做X,他认为Y是解决X的有效途径。
- 他也不知道Y怎么做。
- 他向他人寻求帮助,如何做Y
- 其他人尝试帮助他解决问题Y,但是感觉Y问题很奇葩。
- 浪费了很长时间后,大家才发现他其实想做X,并不是想做Y。
在回答萌新问题时,这一点尤其重要。首先确保你了解到他的真实意图,搞清楚这一点会节省很多时间。
站在回答者的角度,搞清楚 X-Y问题
,引导提问者找出其提问的本质问题,可以节省时间。
站在提问者的角度,讲究 提问的智慧
,可以节省双方的时间。
Tip
这周没有专题性的总结,记录一些零散的技巧
- 不懂的英文单词,google
define xxxx
会返回单词的英文解释(学更多单词,也能了解到哪些是高频基础词汇)
Share
- https://www.imooc.com/learn/117
- 数据库设计与优化。每节几分钟,讲解基础概念和实践原理。讲的很清晰,适合有一定经验的开发人员。
- 《信息简史》
- 本书对思维的冲击很大。相信你看这本书的时候,也会有打开新世界大门的感觉。
- 长度、重量、温度等等都有自己的测量单位,bit 是测量信息的单位。身处于21世纪信息社会,不了解信息的历史怎么行。
- 学习一门技术,必定要了解其发展历史,知晓技术产生的前因后果。这样才能体会到技术的精髓所在,正所谓 "以史为镜,可知兴替"。
注:
- 部分 tip 和 share 都是在看耗子叔专栏(金库)时记下来的。
- 目前 arts 以文章的形式组织内容,有点不好检索,后面可能考虑拆分为表格。