### wretched's blog

By wretched, history, 13 months ago,

Recently,I have started to try DP problems.But for this problem(Rooks-lightoj 1005) though I have already thought much but I am not getting any idea how can i solve this problem by using DP technique.Can anyone help me what's the actual idea behind this problem!!

• +1

 » 13 months ago, # |   0 Say you put rooks in $(r_1, c_1), (r_2, c_2), ... (r_k, c_k)$ positions of the board. What is the condition that no rook attacks another one? Spoiler$r_1 \neq r_2 \neq ... \neq r_k$ and $c_1 \neq c_2 \neq ... \neq c_k$ So you pick k distinct rows and k distinct columns and put rooks in there. Can you find the formula now? Spoiler${{n}\choose{k}}^2 \times k!$ you can use dp to calculate binomials.
•  » » 13 months ago, # ^ | ← Rev. 3 →   0 if(r1==r2 || c1==c2),then (r1,c1) and (r2,c2) both of will be in attacking position?? I mean row and colomn of two positions won't be same to stay both of rooks in non-attacking position.
 » 13 months ago, # | ← Rev. 2 →   0 You can solve it by using DP by observing the following states.If you are currently at the state (i, j, k) where i and j are the height and width of the chessboard respectively and k is the number of remaining rooks. Initial state would be (n, n, k).There are two types of transitions Placing the rook on the jth row i.e. (i, j, k) to (i-1, j-1, k-1) and removing whole row as well as column from the chessboard as a valid position 2 Not placing it i.e. (i, j, k) to (i, j-1, k).However in the first case if you are placing rook on the jth row there are total of i coulumns where you place it. Therefore dp[i][j][k] = dp[i-1][j-1][k-1]*i + dp[i][j-1][k];I guess you can figure out base cases :)However, it can be used simply solved by using combinatorics as already in the previous comment.
•  » » 13 months ago, # ^ |   0 Thank you very much for your help :)