G家题讨论: harry potter 走矩阵

假设你是harry potter,在grid的左上角,你现在要走到右下角,grid中有

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s