對于這種簡單題，往往都是同類別題的母題最簡化版，一些難題不過是對母題加了各種維度的判斷，從而提升了難度。
這道題是非常經(jīng)典的DP問題，不用DP其實也能做， 但是為了加深對DP的理解，選擇用DP，此前也多次做過這題，但是今天再做時又悟到了些新的東西。
定義狀態(tài)方程前的第一件事就是找題目中的變量，就類似于做應(yīng)用題，把未知變量設(shè)出來，再根據(jù)題目給的限定條件，組合拼接成一個未知式，就能解出問題。（今天新領(lǐng)悟，之前也做了不少動態(tài)規(guī)劃題，只是看到的了狀態(tài)方程 “形”，卻不清楚來龍去脈）
對于本題有三個未知變量：1. 天數(shù) 2. 因只能進(jìn)行一次交易，這得再加一個變量，即當(dāng)天是否持有股票 3.最大利潤，即為最后所求。
狀態(tài)方程的定義要滿足無后效性，即前面的狀態(tài)確定下來以后不會因為后面狀態(tài)而更改。如果只定義一維的話，即dp[i]，表示在第 i 天能獲得的最大利潤，但是卻不知如何從 dp[i-1] 轉(zhuǎn)移到 dp[i]，dp[i-1] 具體表示什么意思呢？
這完全不知道，表示 i-1天 的最大利潤？ 那 i-1 天內(nèi)進(jìn)行了一次還是多次交易呢？這并不知道。所以要加一維，即把第二個變量用起來。dp[i][j] 表示 第 i 天 持有股票狀態(tài)為 j（0：不持有 1: 持有） 的情況下，最大利潤是多少。
第一種情況：dp[i][0]，如何轉(zhuǎn)移？
dp[i][0]，表示第 i 天不持有股票時的最大利潤。可由兩種情況轉(zhuǎn)移
- 前i-1 天不持有股票，即dp[i-1][0]，這也是完全可以的
- 前i-1 天持有股票，即dp[i-1][1]，那么我選擇在今天（第i天）把它賣了，即dp[i-1][1]+prices[i]
第二種情況：dp[i][1]，如何轉(zhuǎn)移？ 這個狀態(tài)是最容易出錯的
dp[i][1]，表示 第 i 天持有股票時的最大利潤，可由兩種情況轉(zhuǎn)移
- 前 i - 1 天持有股票，今天按兵不動，即dp[i-1][1]
- 之前一直沒有股票，但是我今天購入一支股票，不就持有了，這里千萬不能定義成 dp[i-1][0] + prices[i]。為什么呢？再次回到 dp[i][j] 定義，在下標(biāo)為 i 的這一天，用戶手上持股狀態(tài)為 j 所獲得的最大利潤。核心在 “利潤” 上，利潤是怎么來？是不是要一前一后做差才能得到利潤，dp[i-1][0] + prices[i] 表示什么？前i-1天不持有股票，今天購入一支？這完全不對啊，因為我們在此前可能并沒有錢購買股票，我們必須要把股票拋出去才能得到利潤，所以這個狀態(tài)為：0-prices[i]，因為只能進(jìn)行一次交易，所以在進(jìn)行本地交易前，手里是沒有錢的，即沒錢也買，利潤為負(fù)。即-prices[i]。題目并沒有要求利潤不能為負(fù)，-1 總比 -5好。類似于這個點其實很多動態(tài)規(guī)劃題都有這個思路，往往我們?nèi)菀紫氘?dāng)然，導(dǎo)致題做不出來。
public int maxProfit(int[] prices) {
int len = prices.length;
if(len == 0)
return 0;
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];//沒錢也買，即利潤為負(fù)，萬一后面股票高，我一拋，不就賺回來了
for(int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
}
return dp[len-1][0];
}
