24 July 2023
For the past two days, I am trying to solve more questions on Dynamic Programming for a better understanding of the topic.
My approach:
It was clear that we can solve this question by recursion and if there is recursion then there exists a memoized solution and eventually, we can come up with a dynamic programming solution.
My solution:
- Recursion and Memoization
#include <bits/stdc++.h>
int helper(int n,int s, vector<int> &heights, vector<int> &dp) {
if(s>=n){
return 0;
}
if(dp[s]!=-1){
return dp[s];
}
int a = 0;
int b = INT_MAX;
if(s+1<n){
a = helper(n,s+1, heights,dp) + abs(heights[s]-heights[s+1]);
}
if(s+2<n){
b = helper(n,s+2,heights,dp) + abs(heights[s]-heights[s+2]);
}
dp[s] = min(a,b);
return min(a,b);
}
int frogJump(int n, vector<int> &heights)
{
vector<int> dp(n,-1);
return helper(n,0,heights,dp);
}
- Dynamic Programming
int frogJump(int n, vector<int> &heights)
{
vector<int> dp(n);
dp[0] = 0;
dp[1] = abs(heights[0]-heights[1]);
dp[2] = abs(heights[0]-heights[2]);
for(int i=3;i<n;i++){
int a = abs(heights[i]-heights[i-1])+dp[i-1];
int b = abs(heights[i]-heights[i-2])+dp[i-2];
dp[i] = min(a,b);
}
return dp[n-1];
}
My approach:
This question was forming subsequences. For solving a question that involves subsequence. We either include the element in the subsequence or exclude the element in the subsequence. Later, I also realized that we can even optimize the space in the dp solution.
My solution:
- Recursion and Memoization
int helper(vector<int> &nums, int n,int s,vector<int> &dp){
if(s>=n){
return 0;
}
if(dp[s]!=-1){
return dp[s];
}
int a = nums[s];
int b = nums[s];
if(s+2<n){
a +=helper(nums,n,s+2,dp);
}
if(s+1<n){
b = helper(nums,n,s+1,dp);
}
dp[s] = max(a,b);
return max(a,b);
}
int maximumNonAdjacentSum(vector<int> &nums){
// Write your code here.
int n = nums.size();
vector<int> dp(n,-1);
return helper(nums,n,0,dp);
}
- Dynamic Programming
int maximumNonAdjacentSum(vector<int> &nums){
// Write your code here.
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
dp[1] = max(nums[1],nums[0]);
for(int i=2;i<n;i++){
int a =dp[i-2]+nums[i];
dp[i] = max(a,dp[i-1]);
}
return dp[n-1];
}
- Dynamic Programming with Space Optimization
int maximumNonAdjacentSum(vector<int> &nums){
// Write your code here.
int n = nums.size();
int notAdj = nums[0];
int adj = max(nums[0], nums[1]);
for(int i=2;i<n;i++){
int pick = notAdj+nums[i];
int notPick = adj;
int maxValue = max(pick,notPick);
notAdj = adj;
adj = maxValue;
}
return adj;
}
My approach:
This question is very similar to the previous question. It used the same approach involving subsequences.
My solution:
- Recursion and Memoization
int helper(vector<int> &houses, int n, int s, vector<int> &dp){
if(s>=n){
return 0;
}
if(dp[s]!=-1){
return dp[s];
}
int pick = houses[s]+helper(houses,n,s+2,dp);
int notPick = helper(houses,n,s+1,dp);
dp[s] = max(pick,notPick);
return max(pick,notPick);
}
int maxMoneyLooted(vector<int> &houses, int n)
{
/*
Write your code here.
Don't write main().
Don't take input, it is passed as function argument.
Don't print output.
Taking input and printing output is handled automatically.
*/
vector<int> dp(n,-1);
return helper(houses,n,0,dp);
}
- Dynamic Programming with constant space complexity
int maxMoneyLooted(vector<int> &houses, int n)
{
/*
Write your code here.
Don't write main().
Don't take input, it is passed as function argument.
Don't print output.
Taking input and printing output is handled automatically.
*/
int prevBy2 = houses[0];
int prevBy1 = max(houses[0], houses[1]);
for(int i=2;i<n;i++){
int pick = houses[i]+prevBy2;
int notPick = prevBy1;
int maxValue = max(pick,notPick);
prevBy2 = prevBy1;
prevBy1 = maxValue;
}
return prevBy1;
}
My approach:
This question is the same as before with one condition added of first and last elements are adjacent. This will use the same approach as before we just have to consider the condition accordingly.
My solution:
- Recursive and Memoization
long long int helper(vector<int>& valueInHouse,int n,int s,vector<long long int>& dp){
if(s>=n){
return 0;
}
if(dp[s]!=-1){
return dp[s];
}
long long int pick = valueInHouse[s]+helper(valueInHouse,n,s+2,dp);
long long int notPick = helper(valueInHouse,n,s+1,dp);
dp[s] = max(pick,notPick);
return max(pick,notPick);
}
long long int houseRobber(vector<int>& valueInHouse)
{
// Write your code here.
int n = valueInHouse.size();
if(n==1){
return valueInHouse[0];
}
vector<long long int> dp1(n-1,-1);
vector<long long int> dp2(n,-1);
long long int pickFirst = helper(valueInHouse,n-1,0,dp1);
long long int notPickFirst = helper(valueInHouse,n,1,dp2);
return max(pickFirst,notPickFirst);
}
- Dynamic Programming
long long int helper(vector<int> &houses, int n)
{
long long int prevBy2 = houses[0];
long long int prevBy1 = max(houses[0], houses[1]);
for(int i=2;i<n;i++){
long long int pick = houses[i]+prevBy2;
long long int notPick = prevBy1;
long long int maxValue = max(pick,notPick);
prevBy2 = prevBy1;
prevBy1 = maxValue;
}
return prevBy1;
}
long long int houseRobber(vector<int>& valueInHouse)
{
// Write your code here.
int n = valueInHouse.size();
if(n==1){
return valueInHouse[0];
}
vector<int> dp1,dp2;
for(int i=0;i<n;i++){
if(i!=0){
dp2.push_back(valueInHouse[i]);
}
if(i!=n-1){
dp1.push_back(valueInHouse[i]);
}
}
long long int pickFirst = helper(dp1,n-1);
long long int notPickFirst = helper(dp2,n-1);
return max(pickFirst,notPickFirst);
}
My approach:
It was a pretty simple question. It can easily be solved by using recursion and doing the right calculation.
My solution:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void helper(TreeNode* root, int &sum){
if(root==NULL){
return;
}
if(root->left!=NULL && root->left->left==NULL && root->left->right==NULL){
sum+=root->left->val;
}
helper(root->left,sum);
helper(root->right,sum);
}
int sumOfLeftLeaves(TreeNode* root) {
int sum = 0;
helper(root,sum);
return sum;
}
};