---

title: 'DP problem set-2' topic : 'dynamic-programming' id: 2 description: 'Dynamic programming problem set of 1D dp. problems - House robber and House robber 2' subtopic: ['1d-dp']

DP problem set - 2

Summary for the blog ⌨️⌨️ In this blog of Dynamic programming, we will discuss basic DP problems, we will see the problem solving approach, intuition and the code solution for the problems.

Sl No	Leetcode problems/ Algorithms	Link
1	Maximum sum of non-adjacent elements	Problem 1
2	House Robber II	Problem 1

Problem No - 1 [Maximum sum of non-adjacent elements/ House robber]

Intuition :-

• The basic idea is that if we consider a particular element in the sum we can’t take the adjacent element in the sum.
• Hence we should try out all possible combination and determine the maximum sum among then, trying all possible ways means a recursive way,
• We will iterate the array in the recursion with a index i from n-1 to 0 th index, where n is the length of the array. at every index we can either include the current element in our sum of exclude it form our sum.
• The base case would be if we reach index 0 we would return nums[0] (since we reached index 0 and we want to maximize the sum we will consider the element at index 0 as well), else if the index reached is less than 0, we would return 0 (as no more element can be included from the array to the sum),
• Since the time complexity is 2^n and space complexity if O(n), we would need to optimize it, we will use a technique called memoisation to optimize it.
• In memoisation we will take a 1D array to store the sum of the processed subsequence, which can be used while computing the sum of other subsequence.
• you can explore other technique called tabulation as well.

#include <bits/stdc++.h> 
int solve(int i,vector<int> &nums,vector<int>&dp){
    if(i==0){
        return nums[0];
    }
    if(i<0) return 0;

    if(dp[i]!=-1) return dp[i];

    int take =nums[i]+solve(i-2, nums,dp);
    int notake = solve(i-1, nums,dp);

    return dp[i]= max(take,notake);
}
int maximumNonAdjacentSum(vector<int> &nums){
    // Write your code here.
    int n =nums.size();
    vector<int>dp(n,-1);
    return solve(n-1,nums,dp);
}

---

Problem No - 2 [House Robber II]

Intuition :-

• This is similar to the previous problem, we can’t rob from adjacent houses, and the change is houses are arranged in a circle, hence first and last houses are adjacent.
• The basic idea in this problem is that if we choose first house then we cant choose the last house, and vice versa.
• So we will create two vectors first and second, first will store all element in nums except at index 0, and second will store all elements in nums except at index n-1;
• We would find the maximum sum of both the vectors using the previous problem code and return maximum among them

class Solution {
public:
    int solve(int i, vector<int>& nums, vector<int>& dp) {
        if (i == 0)
            return nums[0];
        if (i < 0)
            return 0;
        if (dp[i] != -1)
            return dp[i];
        int take = nums[i] + solve(i - 2, nums, dp);
        int notake = solve(i - 1, nums, dp);

        return dp[i] = max(notake, take);
    }
    int rob(vector<int>& nums) {
        vector<int> first;
        vector<int> second;
        int n = nums.size();
        vector<int> dp(n, -1);
        if (n == 1)
            return nums[0];
        for (int i = 0; i < n; i++) {
            if (i != 0)
                first.push_back(nums[i]);
            if (i != n - 1)
                second.push_back(nums[i]);
        }

        long long int max1 = solve(n - 2, first, dp);
        dp.assign(dp.size(), -1);
        long long int max2 = solve(n - 2, second, dp);

        return max(max1, max2);
    }
};

---