Take a look at the problem statement, take a look at the boundaries, what about the structure of the solution? How is the solution like? It's a path from the top row to the bottom row, isn't it? So Let's break down the problem to a similar problem with the same shape, Can we? Let's assume we have R rows, Instead of finding the best path from row 1 to row R, let's find the best path from row 1 to row (R-1), if we have the best path from row 1 to row (R-1) can we find the best path from row 1 to row R? Yes of course, if our imaginary best path ends at (R,C) then it has to come from (R-1,C-1) or from (R-1, C) plus the value of (R,C).
So dp[r][c] = max(dp[r-1][c-1], dp[r-1][c]) + a[r][c]. And after filling the table we find the maximum value in the last row.
So dp[r][c] = max(dp[r-1][c-1], dp[r-1][c]) + a[r][c]. And after filling the table we find the maximum value in the last row.
No comments:
Post a Comment