Link to the problem statement
First of all it must be clear that having a fixed number of strokes for each row, the problem can be solved independently for each row, so on a top level we have to decide how many strokes to assign to each row and tell them to solve themselves (paint themselves) and then we choose the best combination. So in order to solve the assignment problem we use dynamic programming.
int g(int row, int strokes)
This is the state of our outer DP, which tells if we have to solve rows in range [0...row] and only have strokes number of strokes left, what would be the minimum number of mispainted cells? So we can assign 0, 1, 2, ..., width assigns to the current row and solve g(row-1, strokes-k) which k is the number of strokes that we have assigned to the current row, in this case what would be the number of mispainted cells for this row? f(row, length-1, k) but what this means?
int f(int row, int idx, int strokes)
This is the state of our inner DP, which means we want to paint row of the picture in range [0...idx] and only have strokes number of strokes left. There are two options for us, first not paint cell at (row, idx), which means cost off(row, idx-1, strokes-1) + 1, or paint cells in range [k...idx] with cost of f(row, k-1, strokes-1) + numberOfCellsDifferent to cell at (row, idx).
Think about base cases yourself. (e.g. where row is -1 or strokes is equal to zero)
First of all it must be clear that having a fixed number of strokes for each row, the problem can be solved independently for each row, so on a top level we have to decide how many strokes to assign to each row and tell them to solve themselves (paint themselves) and then we choose the best combination. So in order to solve the assignment problem we use dynamic programming.
int g(int row, int strokes)
This is the state of our outer DP, which tells if we have to solve rows in range [0...row] and only have strokes number of strokes left, what would be the minimum number of mispainted cells? So we can assign 0, 1, 2, ..., width assigns to the current row and solve g(row-1, strokes-k) which k is the number of strokes that we have assigned to the current row, in this case what would be the number of mispainted cells for this row? f(row, length-1, k) but what this means?
int f(int row, int idx, int strokes)
This is the state of our inner DP, which means we want to paint row of the picture in range [0...idx] and only have strokes number of strokes left. There are two options for us, first not paint cell at (row, idx), which means cost off(row, idx-1, strokes-1) + 1, or paint cells in range [k...idx] with cost of f(row, k-1, strokes-1) + numberOfCellsDifferent to cell at (row, idx).
Think about base cases yourself. (e.g. where row is -1 or strokes is equal to zero)
how can you creat this algorithm
ReplyDelete