題目如下

數(shù)據(jù)范圍

本題使用常規(guī)動(dòng)態(tài)規(guī)劃就行，不過(guò)要注意由于有三個(gè)轉(zhuǎn)移的方向，所以我們對(duì)dp數(shù)組的遍歷應(yīng)該是從上到下 從左到右即按列優(yōu)先遍歷。

通過(guò)代碼

class Solution {
public:int maxMoves(vector<vector<int>>& grid) {int n = grid.size();int m = grid[0].size();vector<vector<int>> dp(n,vector<int>(m,0));int ans = 0;for(int j = 1;j < m;j++){for(int i = 0;i < n;i++){if(j > 0 && grid[i][j] > grid[i][j - 1])dp[i][j] = max(dp[i][j],dp[i][j - 1] + 1);if(j > 0 && i > 0 && grid[i][j] > grid[i - 1][j - 1])dp[i][j] = max(dp[i][j],dp[i - 1][j - 1] + 1);if(j > 0 && i + 1 < n && grid[i][j] > grid[i + 1][j - 1])dp[i][j] = max(dp[i][j],dp[i + 1][j - 1] + 1);             if(dp[i][j] == 0)dp[i][j] = -1000000;//對(duì)于到不了的地方應(yīng)該標(biāo)記以防被后面的塊作為有效路徑算入ans = max(ans,dp[i][j]);}}/*for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){cout << dp[i][j] << " ";}cout << endl;}*/return ans;}
};
//tips 當(dāng)然本題同樣可以利用滾動(dòng)數(shù)組的思想用一維數(shù)組來(lái)存儲(chǔ)上一輪的數(shù)組 這里不多贅述