# Dynamic Programming | High-effort vs. Low-effort Tasks Problem

You are given n days and for each day (di) you could either perform a high effort tasks (hi) or a low effort tasks (li) or no task with the constraint that you can choose a high-effort tasks only if you chose no task on the previous day. Write a program to find the maximum amount of tasks you can perform within these n days.

Examples:

```No. of days (n) = 5
Day      L.E.   H.E
1        1       3
2        5       6
3        4       8
4        5       7
5        3       6
= 3 + 5 + 4 + 5 + 3
= 20
```

Optimal Substructure
To find the maximum amount of tasks done till i’th day, we need to compare 2 choices:

1. Go for high effort tasks on that day, then find the maximum amount of tasks done till (i – 2) th day.
2. Go for low effort task on that day and find the maximum amount of tasks done till (i – 1) th day.

Let high [1…n] be the input array for high effort task amount on i’th day and low [1…n] be the input array for low effort task amount on ith day.
Let max_task (high [], low [], i) be the function that returns maximum amount of task done till ith day, so it will return max(high[i] + max_task(high, low, (i – 2)), low [i] + max_task (high, low, (i – 1)))

Therefore, the problem has optimal substructure property as the problem can be solved using solutions to subproblems.

Overlapping Subproblems
Following is a simple recursive implementation of the High-effort vs. Low-effort task problem. The implementation simply follows the recursive structure mentioned above. So, High-effort vs. Low-effort Task Problem has both properties of a dynamic programming problem.

## C

 `// A naive recursive C program to find maximum ` `// tasks. ` `#include ` ` `  `// Returns the maximum among the 2 numbers ` `int` `max(``int` `x, ``int` `y) ` `{ ` `    ``return` `(x > y ? x : y); ` `} ` ` `  `// Returns maximum amount of task that can be ` `// done till day n ` `int` `maxTasks(``int` `high[], ``int` `low[], ``int` `n) ` `{ ` `    ``// If n is less than equal to 0, then no ` `    ``// solution exists ` `    ``if` `(n <= 0) ` `        ``return` `0; ` ` `  `    ``/* Determines which task to choose on day n, ` `       ``then returns the maximum till that day */` `    ``return` `max(high[n-1] + maxTasks(high, low, (n-2)), ` `              ``low[n-1] + maxTasks(high, low, (n-1))); ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `    ``int` `n = 5; ` `    ``int` `high[] = {3, 6, 8, 7, 6}; ` `    ``int` `low[] = {1, 5, 4, 5, 3}; ` `    ``printf``(``"%dn"``, maxTasks(high, low, n)); ` `    ``return` `0; ` `} `

## Java

 `// A naive recursive Java program  ` `// to find maximum tasks. ` ` `  `class` `GFG{ ` `     `  `    ``// Returns maximum amount of task  ` `    ``// that can be done till day n ` `    ``static` `int` `maxTasks(``int` `high[], ``int` `low[], ``int` `n) ` `    ``{ ` `         `  `        ``// If n is less than equal to 0, ` `        ``// then no solution exists ` `        ``if` `(n <= ``0``) ` `            ``return` `0``; ` ` `  `        ``/* Determines which task to choose on day n, ` `            ``then returns the maximum till that day */` `        ``return` `Math.max(high[n - ``1``] + maxTasks(high, low, (n - ``2``)), ` `                ``low[n - ``1``] + maxTasks(high, low, (n - ``1``))); ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String []args) ` `    ``{ ` `        ``int` `n = ``5``; ` `        ``int` `high[] = {``3``, ``6``, ``8``, ``7``, ``6``}; ` `        ``int` `low[] = {``1``, ``5``, ``4``, ``5``, ``3``}; ` `        ``System.out.println( maxTasks(high, low, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by Ita_c. `

## Python3

 `# A naive recursive Python3 program to  ` `# find maximum tasks.  ` ` `  `# Returns maximum amount of task  ` `# that can be done till day n  ` `def` `maxTasks(high, low, n) : ` `     `  `    ``# If n is less than equal to 0,  ` `    ``# then no solution exists  ` `    ``if` `(n <``=` `0``) : ` `        ``return` `0` ` `  `    ``# Determines which task to choose on day n,  ` `    ``# then returns the maximum till that day  ` `    ``return` `max``(high[n ``-` `1``] ``+` `maxTasks(high, low, (n ``-` `2``)),  ` `               ``low[n ``-` `1``] ``+` `maxTasks(high, low, (n ``-` `1``)));  ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `"__main__"` `:  ` ` `  `    ``n ``=` `5``;  ` `    ``high ``=` `[``3``, ``6``, ``8``, ``7``, ``6``]  ` `    ``low ``=` `[``1``, ``5``, ``4``, ``5``, ``3``] ` `    ``print``(maxTasks(high, low, n));  ` ` `  `# This code is contributed by Ryuga `

## C#

 `// A naive recursive C# program  ` `// to find maximum tasks. ` `using` `System;  ` ` `  `class` `GFG ` `{ ` `     `  `    ``// Returns maximum amount of task  ` `    ``// that can be done till day n ` `    ``static` `int` `maxTasks(``int``[] high, ` `                    ``int``[] low, ``int` `n) ` `    ``{ ` `         `  `        ``// If n is less than equal to 0, ` `        ``// then no solution exists ` `        ``if` `(n <= 0) ` `            ``return` `0; ` ` `  `        ``/* Determines which task to choose on day n, ` `            ``then returns the maximum till that day */` `        ``return` `Math.Max(high[n - 1] +  ` `            ``maxTasks(high, low, (n - 2)), low[n - 1] +  ` `            ``maxTasks(high, low, (n - 1))); ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 5; ` `        ``int``[] high = {3, 6, 8, 7, 6}; ` `        ``int``[] low = {1, 5, 4, 5, 3}; ` `        ``Console.Write( maxTasks(high, low, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by Ita_c. `

## PHP

 ` `

Output :

`20`

It should be noted that the above function computes the same subproblems again and again.
Therefore, this problem has Overlapping Subproblems Property. So the High-effort vs. Low-effort Task Problem has both the properties of a dynamic programming problem.

Dynamic Programming Solution

## C++

 `// A DP based C++ program to find maximum tasks. ` `#include ` ` `  `// Returns the maximum among the 2 numbers ` `int` `max(``int` `x, ``int` `y) ` `{ ` `    ``return` `(x > y ? x : y); ` `} ` ` `  `// Returns maximum amount of task that can be ` `// done till day n ` `int` `maxTasks(``int` `high[], ``int` `low[], ``int` `n) ` `{ ` `    ``// An array task_dp that stores the maximum ` `    ``// task done ` `    ``int` `task_dp[n+1]; ` ` `  `    ``// If n = 0, no solution exists ` `    ``task_dp = 0; ` ` `  `    ``// If n = 1, high effort task on that day will ` `    ``// be the solution ` `    ``task_dp = high; ` ` `  `    ``// Fill the entire array determining which ` `    ``// task to choose on day i ` `    ``for` `(``int` `i = 2; i <= n; i++) ` `        ``task_dp[i] = max(high[i-1] + task_dp[i-2], ` `                         ``low[i-1] + task_dp[i-1]); ` `    ``return` `task_dp[n]; ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `    ``int` `n = 5; ` `    ``int` `high[] = {3, 6, 8, 7, 6}; ` `    ``int` `low[] = {1, 5, 4, 5, 3}; ` `    ``printf``(``"%dn"``, maxTasks(high, low, n)); ` `    ``return` `0; ` `} `

## Java

 `// A DP based Java program to find maximum tasks. ` `class` `GFG ` `{ ` `     `  `// Returns the maximum among the 2 numbers ` `static` `int` `max(``int` `x, ``int` `y) ` `{ ` `    ``return` `(x > y ? x : y); ` `} ` ` `  `// Returns maximum amount of task that can be ` `// done till day n ` `static` `int` `maxTasks(``int` `[]high, ``int` `[]low, ``int` `n) ` `{ ` `    ``// An array task_dp that stores the maximum ` `    ``// task done ` `    ``int``[] task_dp = ``new` `int``[n + ``1``]; ` ` `  `    ``// If n = 0, no solution exists ` `    ``task_dp[``0``] = ``0``; ` ` `  `    ``// If n = 1, high effort task on that day will ` `    ``// be the solution ` `    ``task_dp[``1``] = high[``0``]; ` ` `  `    ``// Fill the entire array determining which ` `    ``// task to choose on day i ` `    ``for` `(``int` `i = ``2``; i <= n; i++) ` `        ``task_dp[i] = Math.max(high[i - ``1``] + task_dp[i - ``2``], ` `                        ``low[i - ``1``] + task_dp[i - ``1``]); ` `    ``return` `task_dp[n]; ` `} ` ` `  `// Driver code ` `public` `static` `void` `main(String[] args) ` `{ ` `    ``int` `n = ``5``; ` `    ``int` `[]high = {``3``, ``6``, ``8``, ``7``, ``6``}; ` `    ``int` `[]low = {``1``, ``5``, ``4``, ``5``, ``3``}; ` `    ``System.out.println(maxTasks(high, low, n)); ` `} ` `} ` ` `  `// This code is contributed by Code_Mech. `

## C#

 `// A DP based C# program to find maximum tasks. ` `using` `System; ` ` `  `class` `GFG ` `{ ` `     `  `// Returns the maximum among the 2 numbers ` `static` `int` `max(``int` `x, ``int` `y) ` `{ ` `    ``return` `(x > y ? x : y); ` `} ` ` `  `// Returns maximum amount of task that can be ` `// done till day n ` `static` `int` `maxTasks(``int` `[]high, ``int` `[]low, ``int` `n) ` `{ ` `    ``// An array task_dp that stores the maximum ` `    ``// task done ` `    ``int``[] task_dp = ``new` `int``[n + 1]; ` ` `  `    ``// If n = 0, no solution exists ` `    ``task_dp = 0; ` ` `  `    ``// If n = 1, high effort task on that day will ` `    ``// be the solution ` `    ``task_dp = high; ` ` `  `    ``// Fill the entire array determining which ` `    ``// task to choose on day i ` `    ``for` `(``int` `i = 2; i <= n; i++) ` `        ``task_dp[i] = max(high[i - 1] + task_dp[i - 2], ` `                        ``low[i - 1] + task_dp[i - 1]); ` `    ``return` `task_dp[n]; ` `} ` ` `  `// Driver program to test above function ` `static` `void` `Main() ` `{ ` `    ``int` `n = 5; ` `    ``int` `[]high = {3, 6, 8, 7, 6}; ` `    ``int` `[]low = {1, 5, 4, 5, 3}; ` `    ``Console.WriteLine(maxTasks(high, low, n)); ` `} ` `} ` ` `  `// This code is contributed by mits `

## PHP

 ` ``\$y` `? ``\$x` `: ``\$y``); ` `} ` ` `  `// Returns maximum amount of task that can be ` `// done till day n ` `function` `maxTasks(``\$high``, ``\$low``, ``\$n``) ` `{ ` `    ``// An array task_dp that stores the maximum ` `    ``// task done ` `    ``\$task_dp` `= ``array``(``\$n` `+ 1); ` ` `  `    ``// If n = 0, no solution exists ` `    ``\$task_dp`` = 0; ` ` `  `    ``// If n = 1, high effort task on that day will ` `    ``// be the solution ` `    ``\$task_dp`` = ``\$high``; ` ` `  `    ``// Fill the entire array determining which ` `    ``// task to choose on day i ` `    ``for` `(``\$i` `= 2; ``\$i` `<= ``\$n``; ``\$i``++) ` `        ``\$task_dp``[``\$i``] = max(``\$high``[``\$i` `- 1] + ``\$task_dp``[``\$i` `- 2], ` `                        ``\$low``[``\$i` `- 1] + ``\$task_dp``[``\$i` `- 1]); ` `    ``return` `\$task_dp``[``\$n``]; ` `} ` ` `  `// Driver code ` `{ ` `    ``\$n` `= 5; ` `    ``\$high` `= ``array``(3, 6, 8, 7, 6); ` `    ``\$low` `= ``array``(1, 5, 4, 5, 3); ` `    ``echo``(maxTasks(``\$high``, ``\$low``, ``\$n``)); ` `} ` ` `  `// This code is contributed by Code_Mech. `

Output:

```20
```

Time Complexity : O(n)

## tags:

Dynamic Programming Dynamic Programming