---

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.

Sl No	Leetcode problems/ Algorithms	Link
1	Ninja’s Training	Problem 1
2	Unique Paths	Problem 2

Problem No - 1 [Ninja’s Training]

Intuition :-

• 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>
int solve(int i,int n,int prev,vector<vector<int>> &points,vector<vector<int>>&dp){
    if(i==n) return 0;

    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;
}
int ninjaTraining(int n, vector<vector<int>> &points)
{
    // Write your code here.
    int prev =3;
    vector<vector<int>>dp(n,vector<int>(4,-1));
    return solve(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>
int solve(int i, int j, int m, int n, vector<vector<int>> &dp) {
  if (i == m - 1 && j == n - 1)
    return 1;
  if (i >= m || j >= n)
    return 0;

  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;
}
int uniquePaths(int m, int n) {
  // Write your code here.
  vector<vector<int>> dp(m, vector<int>(n, -1));
  return solve(0, 0, m, n, dp);
}

---