canvas-20201014.png
对于这种简单题，往往都是同类别题的母题最简化版，一些难题不过是对母题加了各种维度的判断，从而提升了难度。
这道题是非常经典的DP问题，不用DP其实也能做， 但是为了加深对DP的理解，选择用DP，此前也多次做过这题，但是今天再做时又悟到了些新的东西。
定义状态方程前的第一件事就是找题目中的变量，就类似于做应用题，把未知变量设出来，再根据题目给的限定条件，组合拼接成一个未知式，就能解出问题。（今天新领悟，之前也做了不少动态规划题，只是看到的了状态方程 “形”，却不清楚来龙去脉）
对于本题有三个未知变量：1. 天数 2. 因只能进行一次交易，这得再加一个变量，即当天是否持有股票 3.最大利润，即为最后所求。
状态方程的定义要满足无后效性，即前面的状态确定下来以后不会因为后面状态而更改。如果只定义一维的话，即dp[i]，表示在第 i 天能获得的最大利润，但是却不知如何从 dp[i-1] 转移到 dp[i]，dp[i-1] 具体表示什么意思呢？
这完全不知道，表示 i-1天 的最大利润？ 那 i-1 天内进行了一次还是多次交易呢？这并不知道。所以要加一维，即把第二个变量用起来。dp[i][j] 表示 第 i 天 持有股票状态为 j（0：不持有 1: 持有） 的情况下，最大利润是多少。
第一种情况：dp[i][0]，如何转移？
dp[i][0]，表示第 i 天不持有股票时的最大利润。可由两种情况转移
- 前i-1 天不持有股票，即dp[i-1][0]，这也是完全可以的
- 前i-1 天持有股票，即dp[i-1][1]，那么我选择在今天（第i天）把它卖了，即dp[i-1][1]+prices[i]
第二种情况：dp[i][1]，如何转移？ 这个状态是最容易出错的
dp[i][1]，表示 第 i 天持有股票时的最大利润，可由两种情况转移
- 前 i - 1 天持有股票，今天按兵不动，即dp[i-1][1]
- 之前一直没有股票，但是我今天购入一支股票，不就持有了，这里千万不能定义成 dp[i-1][0] + prices[i]。为什么呢？再次回到 dp[i][j] 定义，在下标为 i 的这一天，用户手上持股状态为 j 所获得的最大利润。核心在 “利润” 上，利润是怎么来？是不是要一前一后做差才能得到利润，dp[i-1][0] + prices[i] 表示什么？前i-1天不持有股票，今天购入一支？这完全不对啊，因为我们在此前可能并没有钱购买股票，我们必须要把股票抛出去才能得到利润，所以这个状态为：0-prices[i]，因为只能进行一次交易，所以在进行本地交易前，手里是没有钱的，即没钱也买，利润为负。即-prices[i]。题目并没有要求利润不能为负，-1 总比 -5好。类似于这个点其实很多动态规划题都有这个思路，往往我们容易想当然，导致题做不出来。
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];//没钱也买，即利润为负，万一后面股票高，我一抛，不就赚回来了
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];
}
