Paint the Stairs

In the naive approach, we can recursively explore all the valid ways and then count each of the ways. We can use backtracking to find all the ways. For any ‘X’th stair if that stair is of color red then for the ‘X’+1th stair we have only one option and that is to color green. If that stair is of the color green then for the ‘X’+1th stair we have two options, either color it green or red.

So if colorStair(N, color) is our recursive function then :

If current stair is red:

colorStair(N, red) = colorStair(N-1, green)

Else 

colorStair(N, green) = colorStair(N-1, red) + colorStair(N-1, green)

The base case of this recursive function is if ‘N’ = 0 then we have found a valid combination of colors, so return 1.

The steps are as follows:-

// Recursive function to explore all ways

function countWaysUtil( int n, int prevColor, int mod ):

1. If 'N' is 0 then return 1.
2. If 'prevColor' is 0 then select 1 for the current stair and then recursively call countWaysUtil for ('N'-1)th stair with 1 as 'prevColor'.
3. Else recursively call countWaysUtil for ('N'-1)th stair, first with 0 as 'prevColor' then 1 as 'prevColor', add their values and return it.

function countWays( int n ):

1. Call countWaysUtil function with 'N'th stair as red and 'N'th stair as green Add the total number of ways returned and store it into the 'totalWays' variable.
2. Return the value of 'totalWays' variable.

In the previous approach, we were exploring all the ways, Suppose we have 5 stairs and we need to calculate the total number of ways. We will recursively call (4, green) and (4, red). Now (4, green) will recursively call (3, green) and (3, red). Also (4, red) will call (3, green). If we obverse carefully we are calculating the value for (3, green) more than once. We can optimize this by using a matrix to store the value for (3, green). 

All the recursive states are uniquely identified by 2 parameters here, (‘N’, ‘prevColor’). We can construct a matrix of 2 dimensions to store the value calculated for all recursive states and when we visit that state again we will return the value stored in the matrix.

The steps are as follows:-

// Recursive function to explore all ways

function countWaysUtil( int n, int prevColor, int mod , [ [ int ] ] dp):

1. If 'N' is 0 then return 1.
2. If 'DP[N][prevColor] is not equal to -1 then return the value of DP[N][prevColor].
3. If 'prevColor' is 0 then select 1 for the current stair and then recursively call countWaysUtil for ('N'-1)th stair with 1 as 'prevColor' and store the value returned in 'DP[N][prevColor]'.
4. Else recursively call countWaysUtil for ('N'-1)th stair, first with 0 as 'prevColor' then 1 as 'prevColor', add their values and then store the value in 'DP[N][prevColor]' and return it.

function countWays( int n ):

1. Initialize a 'N' x 2 matrix 'DP' with -1.
2. Call countWaysUtil function with 'N'th stair as red and 'N'th stair as green Add the total number of ways returned and store it into the 'totalWays' variable.
3. Return the value of 'totalWays' variable.

In this approach, For any stair ‘X’, if we can find the number of ways to paint all the stairs from 1 to ‘X’th stair such that the ‘X’th stair is painted red and if we can find a number of ways to paint all the stairs from 1 to ‘X’th stair such that the ‘X’th stair is painted green then the number of ways to paint (‘X’+1) stairs with  (‘X’ + 1)th stair painted with the color green is equal to the number of ways to paint ‘X’th stair red + the number of ways to paint ‘X’th stair green. But since two red stairs cannot be adjacent to each other, so the number of ways to paint the (‘X’+1)th stair red is equal to the number of ways to paint ‘X’th stair green.

For example, if ‘N’ = 3 then the number of ways to paint 1st stair with green is 1, and the number of ways to paint 1st stair with red is 1.

Now the number of ways to paint the 2nd stair with the color green = number of ways to paint the 1st stair red + number of ways to paint the 1st stair green = 1+1 = 2

The number of ways to paint the 2nd stair with the color red = the number of ways to paint the 1st stair green = 1.

Now the number of ways to paint the 3rd stair with the color green = number of ways to paint the 2nd stair red + number of ways to paint the 2nd stair green = 1+2 = 3

The number of ways to paint the 3rd stair with the color red = the number of ways to paint the 2nd stair green = 2.

Hence the total number of ways to paint the 3rd stair = number of ways to paint the 3rd stair with the color green + the number of ways to the 3rd stair with the color red. = 3+2 = 5.

The steps are as follows:-

Function countWays(int n):

1. Initialize two variables 'GREEN' and 'RED' with value 1.
2. Run a loop from 2 to 'N':
   • Store the value of ('i' - 1)th green in 'prevGreen' variable.
   • Update the variable 'GREEN' with the value of 'RED'+ 'GREEN'.
   • Update the variable 'RED' with the value 'prevGreen.
3. Initialize a variable 'totalWays' with the value of 'GREEN' + 'RED'.
4. Return the variable 'totalWays'