# Help in a DP question

Constraint are=
1<= T<=10
1<=K<=N<=100
1<=M<=100
1<=cost(i,j)<=10^9

Sample input-
1
4 2 1
0 0 0 2
100 20
30 59
71 81
9 200

Sample output_
160

Just give me some hints to solve this question ?

Hint is to use the prt sc button. I heard it’s much more convenient for the reader and doesn’t require another device to take a picture of your screen.

3 Likes

@just1star
Yes i think you are really smart but this picture is taken in between some ongoing contest with full screen mode and shortcuts like Win+Printscreen does not work there.

@everule1
Anything?

Can you prove it’s not from an ongoing contest?

1 Like

@everule1
yes this question is from hackerearth paypal challenge
and the contest duration is about 2.5 hours
and you can check the time i have asked this question Let c[i][j] denote the cost of painting the i th building with the color j
Let dp[i][j][k] denote the least cost needed to paint the first i buildings such that the last color was j and the there are were k switches.
dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][J][k-1]\ where\ J!=j) + c[i][j].

For fixed colors
dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][J][k-1]\ where\ J!=j) only if j is the fixed color, else it is infinity.

You can calculate the minimum quickly if you calculate it beforehand, instead of every time you have to use it. Just remember for one of them the minimum will be something else because of J!=j so you have to account for that.

1 Like

thanks @everule1
let me do the implementation , thanks a lot once again

3 Likes

this id was actually logged in to my laptop
and this one in my mobile
so i don’t realize from which one i am asking.

1 Like