title: 'DP problem set-3'
topic : 'dynamic-programming'
id: 3
description: 'Dynamic programming problem set of 2D dp. problems - Ninja’s Training and Unique Paths'
subtopic: ['2d-dp']
DP problem set - 3
Summary for the blog ⌨️⌨️
In this blog of Dynamic programming, we will discuss 2d dp problems, we will see how to tackle these problems, intuition and the codes.
Here the aim is to maximize the merit points of the ninja. you may think of solving the problem with a greedy approach, but it would fail (since grabbing maximum credit points in a day would not give up the maximum it can attain ).
Hence we should try out all possible combination and determine the maximum among them, trying all possible ways means a recursive way,
We will iterate the array in the recursion with a index i from 0 to n th index, where n is the number of days(ie no of rows). and also we would maintain a variable ‘prev’ to track the task done in previous day. at every index we can try 2 tasks (one excluding the previous days task).
initially the prev would be set to 3, indicating no previous task is performed at day 0.
The base case would be if we reach index n we would return 0 (since we reached index n and there is no more days left to train).
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 2D array of size nx4 (since prev can take values 0,1,2,3) to store the maximum merit points calculated in a day with a corresponding previous days task.
you can explore other technique called tabulation as well.
#include<bits/stdc++.h>intsolve(int i,int n,int prev,vector<vector<int>>&points,vector<vector<int>>&dp){if(i==n)return0;int maxi=INT_MIN;if(dp[i][prev]!=-1)return dp[i][prev];for(int j=0;j<3;j++){if(j!=prev){int temp =points[i][j]+solve(i+1, n, j, points,dp); maxi=max(maxi,temp);}}return dp[i][prev]= maxi;}intninjaTraining(int n, vector<vector<int>>&points){// Write your code here.int prev =3; vector<vector<int>>dp(n,vector<int>(4,-1));returnsolve(0,n,prev,points,dp);}
Problem No - 2 [Unique Paths]
Intuition :-
Here the problem is very simple, we just need to travel from (0,0) to (m-1,n-1). and the only move possible is down and right.
we would solve this in a recursive way. we will take two variable i and j initialized to 0.
The base case would be -
→ i==m-1 and j==n-1 , then we would return 1.
→ i≥m or j≥n then we would return 0.
In every index we have 2 possibilities , ie either go down or go right.
We would return the sum of both the possibilities, as we are asked to count the number of ways.
memoisation technique similar to previous problem is implimented.
#include<bits/stdc++.h>intsolve(int i,int j,int m,int n, vector<vector<int>>&dp){if(i == m -1&& j == n -1)return1;if(i >= m || j >= n)return0;if(dp[i][j]!=-1)return dp[i][j];int right =solve(i, j +1, m, n, dp);int down =solve(i +1, j, m, n, dp);return dp[i][j]= right + down;}intuniquePaths(int m,int n){// Write your code here. vector<vector<int>>dp(m,vector<int>(n,-1));returnsolve(0,0, m, n, dp);}
: Hey! is your brain fried of this blog? . Well what about a game with me?