New update is available. Click here to update.

Last Updated: 28 Feb, 2021

Moderate

```
The first line of input contains an integer βTβ denoting the number of test cases.
The next βTβ lines represent the βTβ test cases.
The only line of each test case contains 4 integers denoting βNβ, βXβ, βYβ, and βZβ, where βNβ is the length of the rod and 'X', 'Y', 'Z' are the segments into which a given rod can be cut into.
```

```
For each test case, return the maximum number of cut segments from the given rod.
Print the output of each test case in a separate line.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 50
1 <= N <= 10000
1 <= X, Y, Z <= N
Time Limit: 1 sec
```

Approaches

The key idea is that no maximum cuts that can be made in the rod of length βNβ depend upon Maximum cuts made in shorter length.For βnβ length rod ans depends upon 'Nβ - βXβ, βNβ - βYβ and βNβ - βZβ sizes of the rod.

**Algorithm:**

- Create two base case for recursive function such that if length of rod is 0, then return 0. Also add the case if length of rod is less than 0 return infinity.
- Recursively call the function on βNβ - βXβ, βNβ - βYβ and βNβ - βZβ length rods.
- The answer for βNβ length rod is the max of above 3 recursive βANSβ + 1.
- If the answer is greater than equal to infinity return 0 as it cannot be cut into rods of length βXβ ,βYβ and βZβ. Else return the βANSβ.

The key id is that no maximum cuts that can be made in the rod of length βNβ depend upon Maximum cuts made in shorter length. For βNβ length rod ans depends upon 'Nβ - βXβ, βNβ - βYβ and βNβ - βZβ sizes of the rod. Since it has overlapping subproblems it could be solved by dp.

**Algorithm:**

- Initialize a βDPβ array of size βNβ + 1 with -1 and βDP[0]β with 0 as 0 length rod can be cut into 0 segments.
- Run a loop βi' from 1 to βNβ.
- Check for βXβ that 'i' >= βXβ (the length of rod is greater than βiβ) and βDP[ i - X]β != -1 (It means that rod βiβ - βXβ can be cut into segments of βXβ, βYβ and βXβ if DP[i - X] != -1 ) then βDP[i]β = max('DP[i]', βDP[i - X]β).
- Repeat the previous step for βYβ and βZβ also.
- If βDP[N]β equals -1 means it cannot be cut into segments hence return 0 else return βDP[N]β.