HOUSE ROBBER

 *********************************RECURSION**********************************

import java.util.*;

public class HOUSEROBBER {

    public static int findMaxMoney(int nums[], int i) {

        int n=nums.length;

      if (i>=n) {

        return 0;

      }

      int rob=findMaxMoney(nums, i+2)+nums[i];

      int donotrob=findMaxMoney(nums, i+1);

      return Math.max(rob, donotrob);

    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        System.out.println("Enter number of houses:");

        int n = sc.nextInt();

        int nums[] = new int[n];

        System.out.println("Enter money of each house:");

        for (int i = 0; i < nums.length; i++) {

            nums[i] = sc.nextInt();

        }

        System.out.println("The maximum amount of money that can be robbed:" + findMaxMoney(nums, 0));

    }

}

**********************************MEMOIZATION*****************************

import java.util.*;

public class HouseRobberMEMo {

    public static int rob(int nums[]) {

        int n = nums.length;

        int dp[] = new int[n];

        Arrays.fill(dp, -1);

        int i = 0;

        return findMax(nums, n, dp, i);

    }

    public static int findMax(int nums[], int n, int dp[], int i) {

        if (i >= n) {

            return 0;

        }

        if (dp[i] != -1) {

            return dp[i];

        }

        int rob = findMax(nums, n, dp, i + 2) + nums[i];

        int donotrob = findMax(nums, n, dp, i + 1);

        dp[i] = Math.max(rob, donotrob);

        return dp[i];

    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        System.out.println("Enter number of houses:");

        int n = sc.nextInt();

        int nums[] = new int[n];

        System.out.println("Enter money of each house:");

        for (int i = 0; i < nums.length; i++) {

            nums[i] = sc.nextInt();

        }

        System.out.println("The max amount of money:" + rob(nums));

    }

}

**********************************TABULATION*********************************

import java.util.*;

public class HouseRobberTabulization {

    public static int rob(int[] nums) {

        int n = nums.length;

        int[] dp = new int[n + 1];

        dp[0] = nums[0];

        dp[1] = n > 1 ? Math.max(nums[0], nums[1]) : nums[1];

        for (int i = 2; i < n; i++) {

            int rob = dp[i - 2] + nums[i];

            int donotrob = dp[i - 1];

            dp[i] = Math.max(rob, donotrob);

        }

        return dp[n - 1];

    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        System.out.println("Enter number of houses:");

        int n = sc.nextInt();

        int nums[] = new int[n];

        System.out.println("Enter money of each house:");

        for (int i = 0; i < nums.length; i++) {

            nums[i] = sc.nextInt();

        }

        System.out.println("The max amount of money:" + rob(nums));

    }

}

i