动态规划类题目笔记
买卖K次股票
假设当前天数为i，股价为p。
若此前一直不进行买卖，其最优利润为dp[0] = 0。
若此前只做过1次买入操作，且最优利润为dp[1]，考虑到今天的股价p。
则前i天只做过1次买入操作的最优利润为max(dp[1], dp[0]-p)。dp[0]-p表示如果以此前的最优无操作利润，在今天买入可获得的利润。
若此前只做过1次买入1次卖出操作，且最优利润为dp[2]，考虑到今天的股价p。
则前i天只做过1次买入1次卖出操作的最优利润为max(dp[2], dp[1]+p)。dp[1]+p表示如果以此前的最优1次买入的最优利润在今天卖出可获得的总利润。dp[1]+p更大则表示考虑到今天的价格，在今天卖出更合适。
若此前只做过2次买入1次卖出操作，且最优利润为dp[3]，考虑到今天的股价p。
则前i天只做过2次买入1次卖出操作的最优利润为max(dp[3], dp[2]-p)。dp[2]-p表示如果以此前的最优1次买入1次卖出可得利润的基础上，如果在今天买入可获得的利润。dp[2]-p更大则表示考虑到之前的买卖价格和今天的价格，在今天进行第2次买入要比在之前买入更合适。
若此前只做过2次买入2次卖出操作，且最优利润为dp[4]，考虑到今天的股价p。
则前i天只做过2次买入1次卖出操作的最优利润为max(dp[4], dp[3]+p)。dp[3]+p表示如果以此前的最优2次买入1次卖出的最优利润，在今天卖出可获得的总利润。dp[3]+p更大则表示考虑到今天的价格，在今天卖出更合适。
… …
戳气球
https://leetcode-cn.com/problems/burst-balloons/
使用逆向思维，从戳气球变为安置气球，对于区间[i,j]，遍历[i+1,j-1], 假设每一个位置k为第一插入气球，然后其值加上[i,k]和[k,j]的最优结果。
所有的k中，值最大的即为[i,j]中的最优结果。