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)]

---

If you look at the recurrence

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

It is a k+1-term recurrence which means there are at most k+1 successive terms in the recurrence formula. So for space saving, it might be changed into

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

[codes on Leetcode]https://leetcode.com/problems/partition-array-for-maximum-sum/solutions/4668638/recursive-iterative-dp-sc-o-k-0ms-beats-100/

[Leetcode playList]https://www.youtube.com/watch?v=KHVXYo7LxZE&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk

[Dynamic Programming Playlist]https://www.youtube.com/watch?v=30yq3fmE6E8&list=PLYRlUBnWnd5K_XYUesV9oc6M9ONXII61T

考慮

arr=[1,4,1,5,7,3,6,1,9,9,3], k=4

其過程如下:

maxA=1 at index=0 , dp[1]=1
maxA=4 at index=1 , dp[2]=8
maxA=4 at index=1 , dp[3]=12
maxA=5 at index=3 , dp[4]=20
maxA=7 at index=4 , dp[5]=29
maxA=7 at index=4 , dp[6]=36
maxA=7 at index=4 , dp[7]=42
maxA=7 at index=4 , dp[8]=48
maxA=9 at index=8 , dp[9]=65
maxA=9 at index=8 , dp[10]=74
maxA=9 at index=8 , dp[11]=83