采纳答案成功!
向帮助你的同学说点啥吧!感谢那些助人为乐的人
这个就已经是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) );
}
大赞!
事实上,这个问题可以O(n)的求解,具体可以参见这个问答:http://coding.imooc.com/learn/questiondetail/13951.html
这个课程的官方github有对这个问题逐渐优化的详细代码,
C++见:https://github.com/liuyubobobo/Play-with-Algorithm-Interview/tree/master/09-Dynamic-Programming/Course%20Code%20(C%2B%2B)/04-House-Robber/
Java见:https://github.com/liuyubobobo/Play-with-Algorithm-Interview/tree/master/09-Dynamic-Programming/Course%20Code%20(Java)/04-House-Robber/src
登录后可查看更多问答,登录/注册
课程配套大量BAT面试真题,高频算法题解析,强化训练
1.1k 13
1.2k 12
703 11
1.6k 10
1.2k 10