leetcode 309 号问题的理解与解题思路?
来源：9-4 状态的定义和状态转移 House Robber
triump
2018-10-30
老师，我对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. 这个题我感觉对于第一次接触动规的人比较难吧？我看了别人的思路想了半天才明白，请问，这个题你在做的过程中，有什么好的思路？ 我怎么就想不到呢？是题目做少了，还是自己的思路有偏差？感觉自己与你们这些大神差距很大啊。。。 怎么弥补？
1回答
-
1）理解的对；
2）会比较难，如果你接触的动态规划的问题还只是一二十个甚至是个位数，那是太正常了：）
动态规划本身就是极其灵活的一类算法设计问题，要想比较好的掌握动态规划，多见问题，多总结，多编程，多练习，是唯一的方式。没有捷径。对于做算法竞赛的同学来说，100道动态规划只是入门。即使在Leetcode这个相对偏面试的OJ，动态规划都有117道之多。如果随便做两个问题，就能深刻理解动态规划，那么动态规划就太简单了，早就不是什么难点了。实际上，即使平时练习了上百道动态规划的大神，在算法比赛中随随便便被一道动态规划问题虐死，都是很正常的：）
Leetcode上的动态规划问题参见这里：https://leetcode.com/tag/dynamic-programming/
对动态规划感兴趣，可以从Leetcode刷起。遇见不会的，不用太想破头，直接看别人的思路，关键是自己多总结，慢慢就能形成自己的思路。
加油！：）
182019-04-06
相似问题