算法-动态规划-蒲公英云

算法-动态规划

在LeetCode上有一道题：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
这个题的解决思路之一就是使用动态规划。

那何为动态规划，知乎上这篇文章讲的比较透彻：https://www.zhihu.com/question/39948290/answer/883302989

我总结了一下，什么样的问题适合用动态规划？

如何使用动态规划？

建立状态转移方程
这一步是最难的，大部分人都被卡在这里。这一步没太多的规律可说，只需抓住一个思维：当做已经知道 f(1)~ f(n-1)的值，然后想办法利用它们求得 f(n)。
缓存并复用以往结果
这一步不难，但是很重要。如果没有合适地处理，很有可能就是指数和线性时间复杂度的区别。
按顺序从小往大算

回到LeetCode那道算法题，买卖股票的最佳时机含手续费，最难的就是建立状态转移方程，要找到f(n)与 f(n-1)的关系，从买卖动作上来看，变量太多了。换一个角度，从第n次操作结果来看，就只有两个状态，手上有股票和手上没有股票，这就能够建立状态转移方程：

dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]−fee}  //手上没有股票
dp[i][1]=max{dp[i−1][1],dp[i−1][0]−prices[i]}    //手上有股票

剩下工作，就是遍历，然后用一个二维数组存储结果。

算法-动态规划