Open chaingangway opened 5 years ago
这题用动态规划解，难点就在于怎样定义状态最简单，下面是参考花花酱的解法 hold指第i天还持有股票时的收益:可能是第i-1天持有而来，也可能是第i天才开始买的股票 rest是指第i天啥都不作为且不持股的收益：可能是来于冷冻期，可能是一直不作为 sold指第i天卖掉股票产生的收益：一定来自于第i - 1天持有股票的收益加上第i天卖掉的收益 因此可以得到状态转移方程： hold[i] = max(hold[i - 1], rest[i - 1] - price[i]) rest[i] = max(sold[i - 1], rest[i - 1]) sold[i] = hold[i - 1] + price[i] 最终结果最后一天要么是不作为，要么是卖掉才有可能取到最大值max(rest(i), sold(i)) 初始值：hold[0] = -1 rest[0] = 0 sold[0] = 不存在
建议先从Brute Force的思路开始想起，遍历序列中的每一个单词，对每个单词从左到右取子串，如果原序列中都存在这个单词的子串，那么这个单词就是符合要求的解。优化点：可以把序列化为集合除去重复元素，减少单词的遍历次数；可以在遍历单词之前就判断是否是最优解，减少单词的遍历次数。 还有一种直观的trie树解法，特地复习了一下这个数据结构，但是主流语言中都没有实现好的，貌似Python中有，但是我现在没有时间研究，往后面放一放吧。
best-time-to-buy-and-sell-stock-with-cooldown
这题用动态规划解，难点就在于怎样定义状态最简单，下面是参考花花酱的解法
hold指第i天还持有股票时的收益:可能是第i-1天持有而来，也可能是第i天才开始买的股票
rest是指第i天啥都不作为且不持股的收益：可能是来于冷冻期，可能是一直不作为
sold指第i天卖掉股票产生的收益：一定来自于第i - 1天持有股票的收益加上第i天卖掉的收益
因此可以得到状态转移方程：
hold[i] = max(hold[i - 1], rest[i - 1] - price[i])
rest[i] = max(sold[i - 1], rest[i - 1])
sold[i] = hold[i - 1] + price[i]
最终结果最后一天要么是不作为，要么是卖掉才有可能取到最大值max(rest(i), sold(i))
初始值：hold[0] = -1 rest[0] = 0 sold[0] = 不存在
longest-word-in-dictionary
建议先从Brute Force的思路开始想起，遍历序列中的每一个单词，对每个单词从左到右取子串，如果原序列中都存在这个单词的子串，那么这个单词就是符合要求的解。优化点：可以把序列化为集合除去重复元素，减少单词的遍历次数；可以在遍历单词之前就判断是否是最优解，减少单词的遍历次数。 还有一种直观的trie树解法，特地复习了一下这个数据结构，但是主流语言中都没有实现好的，貌似Python中有，但是我现在没有时间研究，往后面放一放吧。