如何在我的代码中使用回忆录？

Question

class Solution {

    public int rob(int[] nums) {
        return robmax(nums,nums.length-1);    
    }

    public int robmax(int[] nums,int n) {
        int max = 0;
        if(nums.length==0) return 0;
        if(n==1) return Math.max(nums[0],nums[1]);
        if(n==0) return nums[0];
        else{
            max = Math.max(nums[n]+robmax(nums,n-2),robmax(nums,n-1));
        }
        return max;
    }
}

还有，我的算法的运行时复杂度是多少。

Answer 1

您不需要记忆来解决这个问题，也不需要递归调用。动态编程解决方案将工作得很好，而且要简单得多。您可以在元素上一次找到解决方案。考虑以下算法：

• 将最大值初始化为0
• 对于每个房子，您可以抢劫的最大值为：
  • 截至房屋[i-2]的最大值+当前房屋的值
  • 截至house[i-1]
  的最大值

  也就是说，跟踪截止到前一个房子的已知最大值，以及前一个-前一个。当你到达最后一所房子时，你就有了累计的最大总和。这是大纲，我希望我不会破坏练习：

  public int rob(int[] nums) {
      int max = 0;
      int prev = 0;
      int prevprev = 0;
      for (int current : nums) {
          // TODO: 3 lines to solve the puzzle
      }
      return max;
  }