Accepted clean Java DP solution with explanation


  • 1
    public int rob(int[] a) {
      if (a == null || a.length == 0)
        return 0;
      
      // dp(i) represents the max money we can rob till house (i-1)
      // dp(i) = money of house (i-1) + max {previous non-adjacent houses start from i-2}
      int[] dp = new int[a.length + 1];
      dp[1] = a[0];
      
      // at least let's rob one!
      int max = a[0];
      
      for (int i = 2; i <= a.length; i++) {
        for (int j = i - 2; j >= 0; j--) {
          dp[i] = Math.max(dp[i], dp[j] + a[i - 1]);
        }
        
        max = Math.max(max, dp[i]);
      }
      
      return max;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.