算法-动态规划

偏执的太偏执、 2022-12-28 13:00 174阅读 0赞

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

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

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

*  问题的答案依赖于问题的规模，也就是问题的所有答案构成了一个数列。
 *  大规模问题的答案可以由小规模问题的答案递推得到，也就是 f(n)的值可以由 f(i)中的个别求得。

**如何使用动态规划？**

*  建立状态转移方程  
    这一步是最难的，大部分人都被卡在这里。这一步没太多的规律可说，只需抓住一个思维：当做已经知道 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]}    //手上有股票

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

[https_leetcode-cn.com_problems_best-time-to-buy-and-sell-stock-with-transaction-fee]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
[https_www.zhihu.com_question_39948290_answer_883302989]: https://www.zhihu.com/question/39948290/answer/883302989