C++ DP動態規劃解Leetcode 937 Maximum Number of Points with Cost

好,各位好,我們來解今天立課的問題
今天立課的問題是第1937題
所謂的maximum number of points with cost
它是一個中等的題目
實際上來說
它可能要比許多的難題還要困難
不是說難解
而是基於它的一些constraints
好,所以它這邊給定的是一個
m 乘 n 的整數的一個矩陣
直接就叫做 points
它也告訴你是從 0 開始
一開始是從 0 points
那當然你的目的就是要
將你的 points 將它最大化
透過它的一個走法
那怎麼去走法呢?
也就是說
你在每一個 row
你就挑一個 cell
然後就將這個 cell
它在那個 rc 的位置
它會有一個點數 points
rc 你就加到你的 score 裡面
好,那如果只是這樣呢當然蠻簡單的
但是它會有一個
所謂的 penalty 的一個條件
也就是說
你跟上一次
比方說
我們在上一個 row
你已經假設你取得的
在 r, r 這一 row 你已經取得
那現在你要考慮的當然是
r 加 1 的這一 row
那麼呢
上一次假設你的所取的 index 是 r
然後 column 是在 c1
那這一次的你的 column 是 c2
那你就必須要你的 penalty
就是要去減掉
c1 減掉 c2 的絕對值
所以這是它所謂的一個 penalty
因為有了這個 penalty 就讓問題稍微比較複雜一點
下面也告訴你所謂的
絕對值是怎麼算的
這個一般人都知道
那我們就看一下它相關的例題
我們看這邊的例題
第一個例題
那它這邊直接就告訴我們
就循著這個已經畫這個顏色的路徑去走
它就是會得到最大的 score
那我們看一下它是怎麼說的
當然你在一開始的時候
你當然這邊是選一個 3
在 first row 你的第零 row 的地方
然後再選取 5
然後再選取 3
所以你得到的 score 是目前來講
我們還沒有考慮 penalty 的時候
當然就是 11
當你去考慮 penalty 的時候
這邊因為它跟上面一 row
它在 column 地方必須要減 1
這邊呢
跟上一次的 penalty 也要減 1
所以呢
這邊的話就變成 11 要減 2
所以答案是 9
所以我們先了解它一個提議
接下來我們來看例題 2
例題 2 的部分它也是
透過這樣的圖顯示你要走的最佳的路徑
所以在 first row
0th row 你就選 5
再選 3
再選 4
所以它的 penalty 也只有在最後面的地方
所以它這裡所得到的 score 是 5
加 3
加 4
再減 1
所以你很快的算出來
當然你的答案也就是 11
那我們來看一下它相關的 constraint 部分
Constraint 部分當然跟我們解題的方式會有一些關聯
所以你看一下
它是將 points the length
它的長度設為 n
然後每一 row
它應該講它的 column 的個數
column 個數設為 n
這個跟習慣上的可能跟有些人是不一樣
所以如果是這樣的話當然就很清楚
設為 r
這邊設為 c
也可以
比較 subtle 的地方是在這裡
它 m 跟 n 它是小於
15 次方 也就是 10 萬
那 m 乘以 n 它也是小於 15 次方
那這個時候如果你採用所謂的
靜態陣列的話
你這邊都把它設為 10 萬
然後又是 10 萬
那有可能就會造成記憶體的不夠的一個問題
這是有可能
所以在這邊我們為了要避免這樣的情況
我們當然是採用動態配置的方式
所以我們一個陣列是採用動態配置的一個方式
好
那麼
在 points 它的一個範圍
它也是 0 到 10 萬之間
好 它這邊
為什麼會困難呢
你看一下它的
目前的接受的比例
它也只有 36%
稍微多一點而已
那實際上很多難題的
它的接受率要比這個要高很多
所以它這也確實困難
那它這邊也很大方告訴你
你就採用動態規劃的方式
Dynamic Programming 的方式去做
那
DP
IJ 你就設你目前所得到的點數
那當然你就說你有取
在 IJ 的
的那個 points
所以我們原則上也是照這樣的一個方式
去解題
好 接下來我們看看我們一個解題的
過程當中碰到的什麼問題
好 我們這邊先看一個
超過時間的一個解答
它總共是有 157 個
Test Case
那我們能夠通過 152 個
那這邊基本上我們就是採用
遞回加上記憶體
那
主要會出問題的地方是在這裡
因為我們
它裡面總共有一個狀態
它有 R 弱
然後它有 C 個 column
但是因為我們在這邊我們要每次要取
它的所謂的
Maxima
所以在這個地方呢
這個兩個 Loop
所以就會造成
C 的平方
好 所以原則上
像這種解答它的
時間複雜度如果沒有辦法降下來的話
實際上來講的話
就是會造成時間超過的一個問題
好 所以我們在這邊 Penalty 的部分
這邊都有處理
那我們這邊
其實來講
解答正確但是它太慢
所以
重點就是說我們必須要找出方法能夠
算出所謂的
它前一弱
然後再扣掉這個 Penalty
所造成的最大的期
所造成的一個期大值
好 那我們看一看
後來我們是怎麼去解的
解的方式我們可以先看
這個我們要在後來
真的實際去 Run 出來的一個過程
只是加上一些 Outputs
那這個其實蠻方便我們去來看這個問題怎麼解
當然一開始我們先將整個 Points
基本上它就是一個矩陣
所以我們就將它很整齊的列印出來
好 那我們要做的事情
也就是
這個第零弱這個當然已經是固定的
所以原則上呢你就
將這個第零弱的每個 columns
加到所謂它的 DP 的一個陣列裡面
這個應該是沒有很大的問題
然後呢
我們再從
第一弱開始
所以我們開始是從這邊開始
好 這邊開始呢你要去
考慮它前一弱
然後跟你這一弱
它會有一個所謂的 Penalty 的問題
所以我們這邊我們去計算兩個陣列
這兩個陣列是什麼呢
比方說這邊是第零
的 column 它的
右邊
右邊的極大
所以在這邊當然很清楚
這邊的話當然就是十
然後這邊的話當然就一
後面這裡都是一
然後再來我們再考慮
Left
當然就是有從左邊
在它左邊的極大
在這裡的話當然是十
因為我們要考慮 Penalty 的問題
所以在這邊的話就十減一變成九
後面這邊大概八七六五
以此類推
好 那我們再考慮
有 Right 跟 Left 的一個極大
那我們就考慮這兩個當中比較大的
基本上就
再加上
最弱的值
就是我們這一次 DP 所產生的一個值
所以我們的過程大概是這樣
好 那我們當然就循著這樣一個步驟
我們當然就循著這樣這個步驟去做
所以原則上我們當然就考慮
當然就是
我們的前一次的一個情況
所以我們當然我們考慮
如果 Two 的話我們當然是這邊呢我們把
Right 跟 Left 這兩個證據都把它算出來之後呢
我們再取這個 Right 跟 Left
相對位置的極大
然後再加上這邊的值
OK 那再來
若三的情況是在這裡
到最後的地方
你算出來的話
我們發現它的極大是出現在這個地方
33
所以這原則上是我們一個解
解答當中一個很重要的一個步驟
就是你要
去計算 Right 跟 Left
在每若
你要算一次
你當然不能每個 column 都算
每個 column 都算那當然又慢了
所以這邊我們看我們的整個 approach
我們當然前面也講我們的
第一個版本當然就是 recursive
加上記憶體
基本上它可以通過 152 個
即使說你將它改成所謂迭代的一個方式
它也沒有辦法完全成功
所以這個我們就必須要
採用剛剛那樣的一個方式
另起爐竈
基本上我們透過
遞回加上記憶體是可以解的
當然就是考慮你要去
考慮所謂的 Right 跟 Left
分別去取它的一個 maximum
當中這個計算也是
算一次就好了
所以原則上我們在這邊
我們會定義所謂的 Right-Left Mass
這樣的一個函數
基本上就是去每一次
每若我們都去算 Left 跟 Right
特別它只有在什麼時候可以去算呢
就在 j 等於 0 的時候我們再去互交
對每一個 row i 我們都去算
那當中在撰寫的時候要稍微小心一點
就是說原本在 dpi-ej 的地方
你應該還是要把它
用這種遞回的 f 來取代
保證它這個 dp 在這個值是已經算過的
如果不這樣做的話它其實會出錯的
所以這個在遞回版本要稍微注意的地方是在這裡
那我們看一下相關的遞回版本的情況
相關遞回版本呢
當然這邊我們都用 R 跟 C
我們都會讓它變成所謂的成員變數
dp 我們也是讓它變成成員變數
這是一個 2D 的陣列
這邊的話 Left and Right
其實這邊用 One-Dimensional 就夠了
所以我們的 f
就是我們主要要去呼叫的部分
其實就滿簡單的
所以這邊你只要考慮它
Left 跟 Right 在 j 的部分取其大
然後再加上 points 就可以了
重點就是在這個部分
怎麼去計算它的 Right 跟 Left 的 maxima
那我們在這邊的話
如果先算 Left
其實這兩個順序是可以對調的
那我們這邊的話你當然是 Left 零
當然就是它的前一 row 的值
這邊沒有任何的 penalty
循著這個迴圈
j 從 1 到 c-1 的地方
這邊你就考慮到 penalty 的問題
因為你是算它左邊的
所以基本上
它每一次會加一個新的 turn
新的 turn 它有可能會是極大
那這邊減 1 的話
就是將上一次的 Left 在 j-1 的值
再減掉 1 我們再取其 maxima
那另外的 Right 的做法
我們這邊當然也是類似的
只不過就是說它的順序是倒序的
所以這邊的話就是從 c-1 開始
這邊當然 penalty 要減 1
透過這樣的方式
基本上我們應該就可以算出
一個可以接受的解答
那我們再看在呼叫的部分
呼叫的部分當然沒有問題
這邊我們其實 Left 跟 Right
我們這邊都是先把它配置是
None 裡面最小的
其實你配置其他值也無所謂
因為它基本上每一 row 它都會
重新去算一次
所以我們這裡
因為你要取最後一 row 的一個極大
所以我們是透過這樣的方式來做的
當然是比較好的版本
當然就是所謂的迭代的版本
迭代的版本當然甚至你可以考慮
甚至在記憶體上面
可以做一個優化
接下來我們來看優化的迭代的版本
基本上
如果是因為我們採取的程式語言是 C++
那它給我們的 points
它的形態是
int 的 2D 的一個 vector
但是我們的 dp 它的值有可能到 none
所以這個來講要稍微小心一點
所以一開始在第零弱的地方
我們整個就把它抄寫過來
這邊當然就透過迴圈
其他的方式可能反而更複雜
接下來當然就是考慮
所謂的 dp 的一個計算
所以我們這邊 left 跟 right
這兩個部分
我們在這邊的話就先算 right 再算 left
跟剛剛所講的那個步驟都
基本上是一致的
但是我們經過這樣一個順序對調的好處是
在這邊我們其實迴圈就不必用那麼多次
所以我們在這邊更新的部分
我們就可以塞在這個地方
這邊我們用到一個技巧
就是所謂跟 1 這個數字做 AND 計算
基本上它就相同於
module 2 基本上是相同的一個 trick
最後的部分
最後的部分我們再取它最後一弱的一個極大
就得到我們的一個答案
接下來我們就看我們在 Leap curve 上的一個情形
我們在 Leap curve 上加上一些輸出的指令
這個也都是蠻簡單的
所以在這邊的一個過程
也就是我們在這個迴圈
特別是外層迴圈要結束之前
我們就讓它做一個 output 的動作
同時在一開始的時候
我們也將它整個的 points 增加列印出來
那我們讓它 run 一次好了
這邊拉高一點
我們其實可以看到它整個的一個步驟
所以這邊答案就是 9
第一個立體
第二個立體
答案是 11
第三個就是我們剛剛所講的那個例子
它的一個步驟 完整步驟都在這邊
所以是 33
所以這個動態規劃有時候真的是蠻困難的
那我們就先談到這裡
謝謝觀看