Python C++ dp動態規劃解Leetcode 1043 Partition Array for Maximum Sum

Python C++ dp動態規劃解Leetcode 1043  Partition Array for Maximum Sum

如果你看一下遞迴公式

dp[i]=max(ans, dp[i-j]+j*maxA)  for j in  [1...min(i, j)]

它是 k+1 項遞迴，這意味著遞迴公式中最多有 k+1 個連續項。 所以為了節省空間，可以改為

dp[i%k]=max(ans, dp[(i-j)%k]+j*maxA) for j in  [1...min(i, j)]

C++ python用monotonic stack解Leetcode 739 daily temperatures

C++ python用monotonic stack解Leetcode 739 daily temperatures。Stack在程式設計、資料結構的課會教，但monotonic stack就不一定了。Leetcode 739 daily temperatures，題目問天氣要等幾天才會變暖，當然迴圈可用倒序，這個確定後，當然要確保堆疊的頂端所代表的溫度大於temperatures[i]...