您对198号问题的解答是不可以改进一点？20行： for (int j = i; j < n && j

您对198号问题的解答是不可以改进一点？20行： for (int j = i; j < n && j - i<2; j++)

来源：9-4 状态的定义和状态转移 House Robber

heisback

2018-01-06

写回答

2回答

heisback

提问者

2018-01-06

这个就已经是O（n）了，第二层循环最多只执行两次

for( int i = n-2 ; i >= 0 ; i -- ) {

memo[i] = memo[i+1];

for (int j = i; j < n && j-i<2; j++)

memo[i] = max(memo[i], nums[j] + (j + 2 < n ? memo[j + 2] : 0) );

}

liuyubobobo

大赞！

2018-01-06

共1条回复

liuyubobobo

2018-01-06

事实上，这个问题可以O(n)的求解，具体可以参见这个问答：http://coding.imooc.com/learn/questiondetail/13951.html

这个课程的官方github有对这个问题逐渐优化的详细代码，

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

回答 1

回答 3

回答 1

回答 1

回答 1