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.
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>intsolve(int i,vector<int>&nums,vector<int>&dp){if(i==0){return nums[0];}if(i<0)return0;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);}intmaximumNonAdjacentSum(vector<int>&nums){// Write your code here.int n =nums.size(); vector<int>dp(n,-1);returnsolve(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
classSolution{public:intsolve(int i, vector<int>& nums, vector<int>& dp){if(i ==0)return nums[0];if(i <0)return0;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);}introb(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]);}longlongint max1 =solve(n -2, first, dp); dp.assign(dp.size(),-1);longlongint max2 =solve(n -2, second, dp);returnmax(max1, max2);}};
: Hey! is your brain fried of this blog? . Well what about a game with me?