This is my first Blog. I hope, this blog would be useful for the programmers out there. This blog is an extension to a previous CSES DP editorial written by icecuber. The link to the blog is here. It was a great editorial and which inspired me to complete that with these few leftover problems.
Problems covered in this editorial:Counting Towers, Elevator Rides, Counting Tilings, Counting Numbers.
Feel free to point out mistakes
Counting Towers (2413)
dp[i][p]=Number of ways to fill from 0th position till the ith position.
here p denotes the tile at ith position as following:
dp[i][0] => number of ways for the same such that ith position consist of 2 tiles of width 1 each.
dp[i][1] => number of ways for the same such that ith position consist of 1 tile of width 2.
So,recurrence would be:
Time complexity here is O(N) for preprocessing and O(1) for answering each query. So, O(T + N) in total.
Elevator Rides (1653)
its a classical problem of dp with bitmasking. here, I have defined dp as follows:
dp[number of rides][weight on the last elevator used]
So, basically, as number of rides is atmost 20, we can use mask to represent the people we have carried to the top of the building. I have added comments in the code to make it easy to comprehend and understand.
Counting Numbers (2220)
It is a good problem for learning digit DP.
dp state is defined as follows:
dp[ith digit from left][previous digit][leading zeroes][tight]
leading zeroes are the zeroes that come before the first non-zero digit in a number eg:0034, 012.
I have added comments in the code for better understanding. This is a standard digit DP problem.
Counting Tilings (2181)
This is a very interesting classical problem of DP with bitmasking. Here masking is used to represent the blocks currently filled in ith column due to arrangement of blocks on (i-1)th column.
here dp state is defined as follows:
dp[i][mask] = number of ways to fill the grid from ith column to mth column such that the ith column arrangement due to (i-1)th column is represented by mask.
I have added comments in the code for better understanding.