C++Python Greedy DP速解Leetcode 1014 Best Sightseeing Pair

An-Wen Deng
4粉絲
8 次觀看·2024年12月27日
各位好,我們來解今天Leap Code的問題
今天的問題是
1014題
所謂的Best Sightseeing Pair
它題目是屬於中等的題目
實際上來講也並不困難
基本上就是給一個陣列
在I的值代表是
第I個景點的價值
基本上兩個景點
它有所謂的Distance
Distance當然就是它Index的差
當然在這邊來講的話
它並沒有區別I跟J大小
實際上來講應該是J要大於I
Distance我們一般理解是大於等於零
所以它這邊講就是說
一個Pair的兩個景點
當然這邊就告訴你I是小於J
那麼它的兩個景點合起來的
所謂得到的一個分數
就是Values在I的值
加上Values在J的值
然後再加上它的
加上I再減掉J
這邊當然是J是比較大
所以基本上就是一句話
所謂的景點
所謂的Score就是它們的價值的和
然後再減掉它們兩者之間的距離
請你返回最大的Score
兩個景點所形成的Pair當中最大的Score
所以這是它題目的大意
接下來我們看一下它的例題
例題在這邊的話
其實這裡就是
Values 8 1 5 2 6
那在這裡的話
它直接就
I它就選第0個
J就選第2個
所以基本上
這個就是它最大的一個Score
原則上我們其實可以
它直接就告訴我們答案
另外第二個例題是說
它就是一個Pair
因為Pair只有一個
所以當然也就是它了
兩個值相加
然後再減掉它的距離
距離是1
所以1加2再減1
所以等於2
那它的Constraints
它的那個Values的
陣列的長度可以到5萬
那Values的值是1到1000
接下來我們看
我們大概怎麼解這樣的一個問題
那接下來我們先
透過Python來解答
那在這個解答之前
我們先把這個提議
做一個重新詮釋
所謂Score呢
基本上你可以把它
當成就是Values i的值
再加上i
然後再加上Values
在J的值再減掉J
當中當然是i是小於J
我們透過這樣一個方式
然後我們的DP
我們當然可以用
所謂的動態規劃的方式去做
所謂DP基本上就是
當中最大的
當然就是在這個式子當中
解救Values在K
再加上K的值
當K是小於i當中最大的
我們透過這樣的方式來解答
也可以算是一種泰倫演算
那我們看一下
所以我們就照上面
其實我們DP
只要用一個變數就夠了
根本不需要用到陣列
我們一開始的值
兩個值都是0跟0
好
再來一個迴圈
我們i跟x是在Enumerate
是在Value的
i當然是代表它的Index
x代表著Values在i的值
我們透過這樣的方式
所以我們Score
基本上就是取最大的
跟上次最大的來看
所以呢
再跟這次的比較
所以我們DP是
我們式子
左邊這裡的值
再加上
就是上次的DP的值
然後再加上這次的
好
另外
我們的DP當然也要更新
當然就是跟上次的比較
再跟這次的情況再做一個更新
所以我們最後當然是Return回去
當然也就是我們的Score
所以我們的程式真的很簡單
好
我們看看
這樣應該是可以執行
好
那我們這邊稍微把它縮一下好了
所以這兩個Case都是正確的
好
那我們就Submit
基本上它是OK的
好
接下來我們再看看其他的
程式語言的部分
比方說是C++的部分
C++的部分我們大概也是採用類似的一個做法
好
我們讓它執行
Submit
好
C++的部分就零毫秒
好
那我們這個問題就先談到這裡
好
