What is Dynamic programming?

Dynamic Programming is a technique of optimizing over recursion by storing the answer for the overlapping subproblems and using that result for the same problem in the future. So, it saves the time of re-computing the answer for the same problem and helps to reduce the exponential time complexity to polynomial time complexity.

Mention some applications of Dynamic programming?

This programming technique is used for mathematical optimization problems, time-sharing, robotics control, flight control as well as a reliability design problem.

Table of contents

Introduction

Problem statement

Approaches

Complexity analysis

FAQs

Key Takeaways

Last Updated: Mar 27, 2024

Minimum Number of Days in which No Task is Performed

Author Malay Gain

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

Here we will be discussing an interesting problem. We will cover two approaches to solve this problem. First, we will see the native recursive approach and then implement the dynamic programming-based solution using the concept of memoization.

Problem statement

You are given an array consisting of 0,1,2,3 only where the value at ith index represents some specific work that can be done on the ith day.

0 represents no tasks available on that day.

1 represents task type A available for that day.

2 represents task type B available for that day.

3 represents both tasks A and B available for that day. You can perform any one of your choices.

Provided that you can’t perform the same type of task on two consecutive days, you need to find the minimum number of days in which no task is performed.

Input

arr[ ] = { 0, 1, 3, 2 }

Output

minimum days with no task performed = 2

Explanation

On the 0th day, no task is performed as arr[0]=0,i.e count=1. On 1st day, task A can be performed. On the 2nd-day task B can be performed, as pervious day’s task is A. But on the 3rd-day task B can not be performed as the previous day’s task was B. So, no task is performed on the 3rd day. Therefore, count=1+1=2

Note: Please try to solve the problem first and then see the below solution approach.

Approaches

Recursive approach

We will use a recursive function to count the minimum number of days in which no task is performed.

We will pass an argument n to keep track of the current index of the arr[ ] and preTask to keep track of the previous day’s task.

If arr[n]=0, no task is available for that day. So, increase the count of days with no task performed.
If arr[n]=1, task A can be performed. But if the previous day’s task preTask=1, task A can not be performed (as the same type of task on two consecutive days is not allowed). In that case, increase the count and make the recursive call for the next index.

If arr[n]=2, task B can be performed. But if the previous day’s task preTask=2, task B can not be performed. In that case, increase the count and make the recursive call for the next index.

If arr[n]=3, and the previous day’s task preTask=1, task A can not be performed; perform task B. But if the previous day’s task preTask=2, perform task A. If no task is performed on the previous day, perform the task that minimizes the number of days with no task performed.

Code

#include<bits/stdc++.h>
using namespace std;

//recursive approach
int minDays(int arr[],int preTask,int n)
{
if(n==0)
{
return 0;
}

//if no task available
if(arr[n-1]==0)
{
return 1+minDays(arr,0,n-1); //no task performed
}
// task A is available
else if(arr[n-1]==1)
{
//check the last task performed
//if it is also A, then no task performed
if(preTask==1)
{
return 1+minDays(arr,0,n-1);
}

//otherwise task A performed
else
{
return minDays(arr,1,n-1);
}
}

// task B is available
else if(arr[n-1]==2)
{
//check the last task performed
//if it is also B, then no task performed
if(preTask==2)
{
return 1+minDays(arr,0,n-1);
}

//otherwise task B performed
else
{
return minDays(arr,2,n-1);
}
}

else
{
//check the last task performed
//if it is A, perform task B
if(preTask==1)
{
return  minDays(arr,2,n-1);
}
//check the last task performed
//if it is B, perform task A
else if(preTask==2)
{
return  minDays(arr,1,n-1);
}

//otherwise perform the task 
//that minimizes no of days with no task performed
else
{
return min(minDays(arr,2,n-1),minDays(arr,1,n-1));
}

}
}

//driver code

int main()
{
int n=4;
int arr[] = { 0, 1, 3, 2 };

cout<<"minimum days with no task performed : "<<minDays(arr,0,4);
}

You can also try this code with Online C++ Compiler

Run Code

Memoized approach(DP based)

To optimize the recursive approach, we can use the memoization technique to store the previously calculated states and use them to calculate the unknown states. This approach of dynamic programming reduces the repeated calculation of the same state.

Code

#include<bits/stdc++.h>
using namespace std;

//2D array to store dp states

int dp[201][3];
//Dynamic programming approach approach
int minDays(int arr[],int preTask,int n)
{
if(n==0)
{
return 0;
}

if(dp[n][preTask]!=-1)
{
return dp[n][preTask];
}
//if no task available
if(arr[n-1]==0)
{
return dp[n][preTask]=1+minDays(arr,0,n-1); //no task performed
}
// task A is available
else if(arr[n-1]==1)
{
//check the last task performed
//if it is also A, then no task performed
if(preTask==1)
{
return dp[n][preTask]=1+minDays(arr,0,n-1);
}

//otherwise task A performed
else
{
return dp[n][preTask]=minDays(arr,1,n-1);
}
}

// task B is available
else if(arr[n-1]==2)
{
//check the last task performed
//if it is also B, then no task performed
if(preTask==2)
{
return dp[n][preTask]=1+minDays(arr,0,n-1);
}

//otherwise task B performed
else
{
return dp[n][preTask]=minDays(arr,2,n-1);
}
}

else
{
//check the last task performed
//if it is A, perform task B
if(preTask==1)
{
return  dp[n][preTask]=minDays(arr,2,n-1);
}
//check the last task performed
//if it is B, perform task A
else if(preTask==2)
{
return  dp[n][preTask]=minDays(arr,1,n-1);
}

//otherwise perform the task 
//that minimizes no of days with no task performed
else
{
return dp[n][preTask]=min(minDays(arr,2,n-1),minDays(arr,1,n-1));
}

}
}

//driver code

int main()
{
int n=4;
int arr[] = { 0, 1, 3, 2 };

memset(dp, -1, sizeof(dp));
cout<<"minimum days with no task performed : "<<minDays(arr,0,4);
}

You can also try this code with Online C++ Compiler

Run Code

Output

minimum days with no task performed : 2

Complexity analysis

The time complexity of the above approach is O(n) where n is the size of the array and space complexity is also O(n).

FAQs

What is Dynamic programming?
Dynamic Programming is a technique of optimizing over recursion by storing the answer for the overlapping subproblems and using that result for the same problem in the future. So, it saves the time of re-computing the answer for the same problem and helps to reduce the exponential time complexity to polynomial time complexity.
Mention some applications of Dynamic programming?
This programming technique is used for mathematical optimization problems, time-sharing, robotics control, flight control as well as a reliability design problem.

Key Takeaways

This article covered how to find the number of days in which no task is performed.

We highly recommend going through the articles on dynamic programming to grasp the concepts clearly.

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here.

Check out this problem - Count Ways To Reach The Nth Stair

Happy learning!

Live masterclass

System Design Questions Asked at Microsoft, Oracle, PayPal

by Pranav Malik

23 Apr, 2025

01:30 PM

24+ registered

Master DSA to Ace MAANG SDE Interviews

by Saurav Prateek

21 Apr, 2025

01:30 PM

474+ registered

Google Data Analyst roadmap: Essential SQL concepts

by Maaheen Jaiswal

22 Apr, 2025

01:30 PM

1020+ registered

Amazon Data Analyst: Advanced Excel & AI Interview Tips

by Megna Roy

24 Apr, 2025

01:30 PM

169+ registered

System Design Questions Asked at Microsoft, Oracle, PayPal

by Pranav Malik

23 Apr, 2025

01:30 PM

24+ registered

Master DSA to Ace MAANG SDE Interviews

by Saurav Prateek

21 Apr, 2025

01:30 PM

474+ registered

View more events