微信小程序怎么做商城_界面设计风格_网络推广外包公司干什么的_企业培训师资格证

题目如下

数据范围

本题使用常规动态规划就行，不过要注意由于有三个转移的方向，所以我们对dp数组的遍历应该是从上到下 从左到右即按列优先遍历。

通过代码

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;//对于到不了的地方应该标记以防被后面的块作为有效路径算入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 当然本题同样可以利用滚动数组的思想用一维数组来存储上一轮的数组 这里不多赘述