APCS202310第4題 投資遊戲

zerojudge連結：https://zerojudge.tw/ShowProblem?problemid=m373

解題策略：DP，DP程式簡單，但要想出解法，不好想。這題要對DP很熟悉，且要能夠定義dp陣列的意義，避免重複計算，有一定的難度，參考以下吳教授的解。

參考：https://hackmd.io/@bangyewu/SkxXo4QGa

一、前言--最大子陣列DP解

v[i]為輸入的每一天獲利

dp[i]為第i天結束的最大獲利

相當於此題的K=0

dp[0] = max(0,v[0])

dp[i] = max(dp[i-1],0)+v[i]

二、定義陣列的意義

K>0

dp[j][i] 為第i天結束的最大獲利，且金牌使用小於等於j個，因為負值的天數可以小於j個

三、狀態轉移

第i天不使用金牌，表示要加上第i天的獲利v[i]。

dp[j][i] = dp[j][i-1]+v[i]

第i天使用金牌，表示要不考慮第i天的獲利v[i]。

dp[j][i] = dp[j-1][i-1]

dp[j][i] = max(dp[j-1][i-1], dp[j][i-1]+v[i])，由上到下由左到右填表，就可以獲得

dp[k]該列所有元素的最大值就是答案

初始化邊界(相當於K=0，最大子陣列DP解)

dp[0][0] = max(0,v[0])

dp[0][i] = max(dp[0][i-1],0)+v[i]