主要讲解的是以动态规划的方式来解决算法问题，虽然部分题目也可以使用其他更加快速方法解决，但本篇关注的是动态规划的思想
Best Time to Buy and Sell Stock
只能买卖一次，求最大利润
从前往后遍历数组，求第i天卖出可以获得的最大利润，即第i天的价格（卖出） - 第1~i-1天最低的价格（买入）。
状态转移方程：
max_profit[i] = max(price[i] - min_buy_price[i-1], max_profit[i-1])min_buy_price[i] = min(price[i], min_buy_price[i-1])
import unittest
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) < 2:
return 0
max_profit = 0
min_buy_price = prices[0]
for price in prices:
if price > min_buy_price:
max_profit = max(max_profit, price - min_buy_price)
else:
min_buy_price = min(min_buy_price, price)
return max_profit
class TestSolution(unittest.TestCase):
def setUp(self):
self.s = Solution()
def test_one(self):
input = [7, 1, 5, 3, 6, 4]
self.assertEqual(self.s.maxProfit(input), 5)
def test_two(self):
input = [7, 6, 4, 3, 1]
self.assertEqual(self.s.maxProfit(input), 0)
if __name__ == "__main__":
unittest.main()
Best Time to Buy and Sell Stock II
允许多次买卖，求最大利润
第i天有2种状态：拥有股票own[i]，未拥有股票no_own[i]，那么其状态方程可以表示为：
- 在当天过后手头拥有股票的条件下，有两种情况：①当天买入的；②当天没有操作，之前买入的；
own[i] = max(own[i-1], no_own[i-1] - price[i]) - 在当天过后手头未拥有股票的条件下，有两种情况：①当天卖出的；②当天没有操作，之前卖出的；
no_own[i] = max(own[i-1] + price[i], no_own[i-1])
状态转移方程：
own[i] = max(own[i-1], no_own[i-1] - price[i])no_own[i] = max(own[i-1] + price[i], no_own[i-1])
import unittest
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) < 2:
return 0
own = [0] * len(prices)
no_own = [0] * len(prices)
own[0] = -prices[0]
for i in range(1, len(prices)):
own[i] = max(own[i-1], no_own[i-1] - prices[i])
no_own[i] = max(no_own[i-1], own[i] + prices[i])
return no_own[-1]
class TestSolution(unittest.TestCase):
def test_one(self):
prices = [7,1,5,3,6,4]
s = Solution()
print(s.maxProfit(prices))
def test_two(self):
prices = [1, 2, 3, 4, 5]
s = Solution()
print(s.maxProfit(prices))
if __name__ == "__main__":
unittest.main()
Best Time to Buy and Sell Stock III
最多两次的任意买卖，求最大利润
第i天有2种状态，k表示这是第k次来回交易：拥有股票own[k][i]，未拥有股票no_own[k][i]，那么其状态方程可以表示为：
- 在当天过后手头拥有股票的条件下，有两种情况：①当天是第k次轮回买入的；②当天没有操作，之前第k次买入的；
own[k][i] = max(own[k][i-1], no_own[k-1][i-1] - price[i]) - 在当天过后手头未拥有股票的条件下，有两种情况：①当天是第k次轮回卖出的，即在之前第k次轮回买入的基础上计算；②当天没有操作，之前第k次轮回卖出的；
no_own[k][i] = max(own[k][i-1] + price[i], no_own[k][i-1])
状态转移方程：
own[k][i] = max(own[k][i-1], no_own[k-1][i-1] - price[i])no_own[k][i] = max(own[k][i-1] + price[i], no_own[k][i-1])
import unittest
from pprint import pprint
class Solution:
def maxProfit(self, prices):
if len(prices) < 2:
return 0
length = len(prices)
own = [[0]*(length) for i in range(3)]
no_own = [[0]*(length) for i in range(3)]
own[1][0] = own[2][0] = -prices[0]
for k in range(1,3):
for j in range(1, length):
own[k][j] = max(own[k][j-1], no_own[k-1][j-1] - prices[j])
no_own[k][j] = max(no_own[k][j-1], own[k][j-1] + prices[j])
return no_own[-1][-1]
class TestSolution(unittest.TestCase):
def setUp(self):
self.s = Solution()
def test_one(self):
input = [3, 3, 5, 0, 0, 3, 1, 4]
self.assertEqual(self.s.maxProfit(input), 6)
def test_two(self):
input = [1, 2, 3, 4, 5]
self.assertEqual(self.s.maxProfit(input), 4)
if __name__ == "__main__":
unittest.main()
Best Time to Buy and Sell Stock IV
最多k次的任意买卖，求最大利润
同上，不过由于k可能较大，为了节省空间，我们利用k%2来节省空间，因为每第k次交易只与上一次交易有关。
仅仅就行上面的优化是不够的，因为k可能大，单当k>=len(prices)//2时，就转化为Best Time to Buy and Sell Stock II的问题了，这样减少了许多计算量。
import unittest
class Solution:
def maxProfit(self, k, prices):
if len(prices) < 2:
return 0
length = len(prices)
if k >= length//2:
own = [0] * length
no_own = [0] * length
own[0] = -prices[0]
for i in range(1, length):
own[i] = max(own[i-1], no_own[i-1] - prices[i])
no_own[i] = max(no_own[i-1], own[i] + prices[i])
return no_own[-1]
own = [[0]*(length) for i in range(2)]
no_own = [[0]*(length) for i in range(2)]
own[0][0] = own[1][0] = -prices[0]
for k in range(0, k):
k = k % 2
own[k][0] = -prices[0]
for j in range(1, length):
own[k][j] = max(own[k][j-1], no_own[k-1][j-1] - prices[j])
no_own[k][j] = max(no_own[k][j-1], own[k][j-1] + prices[j])
return max(no_own[0][-1], no_own[1][-1])
class TestSolution(unittest.TestCase):
def setUp(self):
self.s = Solution()
def test_one(self):
input = [2, 4, 1]
self.assertEqual(self.s.maxProfit(2,input), 2)
def test_two(self):
input = [3, 2, 6, 5, 0, 3]
self.assertEqual(self.s.maxProfit(2, input), 7)
def test_three(self):
input = [1, 2]
self.assertEqual(self.s.maxProfit(1, input), 1)
if __name__ == "__main__":
unittest.main()
Best Time to Buy and Sell Stock with Cooldown
可以进行任意次交易，但卖出股票的第二天不允许进行交易
第i天有2种状态：拥有股票own[i]，未拥有股票no_own[i]，那么其状态方程可以表示为：
- 在当天过后手头拥有股票的条件下，有两种情况：①当天买入的，由于条件限制，因此只能在第i-1之前卖出；②当天没有操作，之前买入的；
own[i] = max(own[i-1], no_own[i-2] - price[i]) - 在当天过后手头未拥有股票的条件下，有两种情况：①当天卖出的；②当天没有操作，之前卖出的；
no_own[i] = max(own[i-1] + price[i], no_own[i-1])
状态转移方程：
own[i] = max(own[i-1], no_own[i-2] - price[i])no_own[i] = max(own[i-1] + price[i], no_own[i-1])
import unittest
class Solution:
def search(self, nums, target):
if len(nums) == 0:
return -1
l = 0
h = len(nums) - 1
while l < h:
m = l + (h-l)//2
if nums[m] <= target:
l = m + 1
elif nums[m] >= target:
h = m
pos = -1
if nums[l] > target:
pos = l
return pos
class TestSolution(unittest.TestCase):
def setUp(self):
self.s = Solution()
def test_one(self):
input = [-1, 0, 3, 3, 5, 9, 12]
self.assertEqual(self.s.search(input, 3), 4)
def test_two(self):
input = [-1, 0, 3, 3, 5, 9, 12]
self.assertEqual(self.s.search(input, 2), 2)
def test_three(self):
input = [0]
self.assertEqual(self.s.search(input, 0), -1)
if __name__ == "__main__":
unittest.main()
Best Time to Buy and Sell Stock with Transaction Fee
可以交易任意多笔，但每次买卖需要支付一定的费用fee
第i天有2种状态：拥有股票own[i]，未拥有股票no_own[i]，那么其状态方程可以表示为：
- 在当天过后手头拥有股票的条件下，有两种情况：①当天买入的；②当天没有操作，之前买入的；
own[i] = max(own[i-1], no_own[i-1] - price[i]) - 在当天过后手头未拥有股票的条件下，有两种情况：①当天卖出的，此时需要支付交易费；②当天没有操作，之前卖出的；
no_own[i] = max(own[i-1] + price[i] - fee, no_own[i-1])
状态转移方程：
own[i] = max(own[i-1], no_own[i-1] - price[i])no_own[i] = max(own[i-1] + price[i] - fee, no_own[i-1])
import unittest
class Solution:
def maxProfit(self, prices, fee):
"""
:type prices: List[int]
:type fee: int
:rtype: int
"""
length = len(prices)
if len(prices) < 2:
return 0
last_own = -prices[0]
last_no_own = 0
for i in range(1, length):
own = max(last_own, last_no_own - prices[i])
last_no_own = max(last_no_own, last_own + prices[i] - fee)
last_own = own
return last_no_own
class TestSolution(unittest.TestCase):
def setUp(self):
self.s = Solution()
def test_one(self):
input = [1, 3, 2, 8, 4, 9]
self.assertEqual(self.s.maxProfit(input, 2), 8)
def test_two(self):
pass
if __name__ == "__main__":
unittest.main()
总结
一开始做这些题的时候，不知道从何下手，但经过这几道题的训练之后，对于大部分的动态规划还是能分析出来，只要状态方程推导出来以后，确定好初始值，就可以得到最终的结果。
