leetcode 309 号问题的理解与解题思路?

Question

老师，我对309 的理解如下：
对于第i 天，要么持有股票，要么不持有股票，下面是别人写的转移方程：也看了你的代码，跟这个如出一辙。
sdp[i] = Math.max(sdp[i-1],bdp[i-1] + prices[i]);
bdp[i] = Math.max(bdp[i-1],sdp[i-2] - prices[i]);
我的理解是 sdp[i] : 表示的是前i 天，股票最后一次是卖出状态时候的最大利润，同理，bdp[i] 表示的是 前i 天，股票最后一次是持有状态时候的最大利润。
我的问题： 1. 理解对么？ 2. 这个题我感觉对于第一次接触动规的人比较难吧？我看了别人的思路想了半天才明白，请问，这个题你在做的过程中，有什么好的思路？ 我怎么就想不到呢？是题目做少了，还是自己的思路有偏差？感觉自己与你们这些大神差距很大啊。。。 怎么弥补？

Answer 1

liuyubobobo 2018-10-30 17:15:30

1）理解的对；

2）会比较难，如果你接触的动态规划的问题还只是一二十个甚至是个位数，那是太正常了：）

动态规划本身就是极其灵活的一类算法设计问题，要想比较好的掌握动态规划，多见问题，多总结，多编程，多练习，是唯一的方式。没有捷径。对于做算法竞赛的同学来说，100道动态规划只是入门。即使在Leetcode这个相对偏面试的OJ，动态规划都有117道之多。如果随便做两个问题，就能深刻理解动态规划，那么动态规划就太简单了，早就不是什么难点了。实际上，即使平时练习了上百道动态规划的大神，在算法比赛中随随便便被一道动态规划问题虐死，都是很正常的：）

Leetcode上的动态规划问题参见这里：https://leetcode.com/tag/dynamic-programming/

对动态规划感兴趣，可以从Leetcode刷起。遇见不会的，不用太想破头，直接看别人的思路，关键是自己多总结，慢慢就能形成自己的思路。

加油！：）

• 提问者 triump #1

  非常感谢！

• 提问者 triump #2

  谢谢你的建议，我通过听你的课才第一次接触动态规划，做过的题就三四道吧  
  。
  另外你的线性代数的课已买，机器学习的课程等腾出时间就买，继续支持你, 希望你能推出更多的好课！

• liuyubobobo 回复 提问者 triump #3

  谢谢你的支持：）通过你的问题，我觉得你的整体基础不错，如果对机器学习感兴趣，可以直接学习我的机器学习的课程：）加油！

点开查看后面5条评论