626
（undone）動態規劃-題目1537：買賣股票
題目1537：買賣股票
時間限製：1 秒內存限製：128 兆特殊判題：否提交：616解決：164
題目描述：
給定一個大小為n的數組，數組的元素a[i]代表第i天的股票價格。
設計一個算法，計算在最多允許買賣k次（一買一賣記為一次）的條件下的最大收益。
需要注意的是，你不能同時擁有兩份股票。也就是說在下次買入前，你必須把手頭上原有的股票先賣掉。
輸入：
輸入可能包含多個測試案例。
對於每個測試案例，輸入的第一行為兩個整數n和k(1<=n,k<=1000)。
輸入的第二行包括n個整數，範圍在[0,10000)，代表數組中的元素。
輸出：
對應每個測試案例，輸出最大獲益。
樣例輸入：
5 1
3 4 5 1 4
7 2
1 2 3 5 6 1 7
樣例輸出：
3
11
來源：
Leetcode 加強版本
思路
動態規劃，用f[i,j]表示前i天交易j次能得到的最多的錢數(還是至多交易j次？)
F[i,j] = max(f[i,j-1], f[i-1,j], f[k-1,j-1]+a[i]-a[k] ( k<i) )
這是一個O(N^3)的方程，所以直接TLE了，注意到轉移過程中的f[k-1,j-1]-a[k]相對k是不變的，所以考慮直接在計算過程中存下f[k-1,j-1]-a[k]的最大值，動態規劃過程中直接使用，
最後更新：2017-04-03 12:55:36