# PROBLEM LINK:

**Author:** Puneet Gupta

**Editorialist:** Puneet Gupta

# DIFFICULTY:

MEDIUM

# PREREQUISITES:

DP

# PROBLEM:

Given the values of n1, n2, k1, k2 we need to find the number of possible permutations of arranging n1 footmen + n2 horsemen such that there are strictly no more that k1 footmen standing successively one after another, or there are strictly no more than k2 horsemen standing successively one after another.

# EXPLANATION:

The problem is solved lazy dynamics. Let `z[n1] [n2] [2]`

be the number of ways to place troops in a legion of Caesar.

Indicate the following parameters, `n1`

– is the number of footmen, `n2`

– is the number of horseman, the third parameter indicates what troops put Caesar in the beginning of the line.

If Caesar wants to put the footmen, the state dynamics of the `z [n1] [n2] [0]`

go to the state `z [n1] [n2 - i] [0]`

, where `0 <= i <= min (k1, n1)`

.

If Caesar wants to put the horsemen, the state dynamics of the `z [n1] [n2] [1]`

go to the state `z [n1] [n2 - i] [1]`

, where `0 <= i <= min (k2, n2)`

.

# AUTHOR’S SOLUTION:

Author’s solution can be found here.