G家题讨论： harry potter 走矩阵 | Hello World
假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
走到右下角。每一步只能向右或者向下。
This is a typical DP problem.
We need to have a dp matrix that is the same size as the matrix.
dp[i][j] stores the strength left after applying the strength[i][j];
So dp[i][j] = 1;
Then we scan line by line from bot to top.
dp[i][j] = Math.min(1-strength[i+1][j], 1- strength[i][j+1]);
Tip: for harry potter at [i][j]. you need to make sure when you step into the down or right, you will need at least 1 strength at one of the 2 directions.
final result will be dp[0][0] �C strength[0][0];
Make sure to take negative numbers into consideration
Read full article from G家题讨论： harry potter 走矩阵 | Hello World
No comments:
Post a Comment