G家题讨论: harry potter 走矩阵

假设你是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] – strength[0][0];
Make sure to take negative numbers into consideration

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s