leetcode 2684. 矩阵中移动的最大次数

标题如下

数据范围

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

复制代码

通过代码

1. class Solution {
2. public:
3.     int maxMoves(vector<vector<int>>& grid) {
4.         int n = grid.size();
5.         int m = grid[0].size();
6.         vector<vector<int>> dp(n,vector<int>(m,0));
7.         int ans = 0;
8.      
9.         for(int j = 1;j < m;j++){
10.             for(int i = 0;i < n;i++){
11.                
12.                 if(j > 0 && grid[i][j] > grid[i][j - 1])dp[i][j] = max(dp[i][j],dp[i][j - 1] + 1);
13.                 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);
14.                 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;
15.                 //对于到不了的地方应该标记以防被后面的块作为有效路径算入
16.                 ans = max(ans,dp[i][j]);
17.                
18.             }
19.             
20.         }
21.         /*for(int i = 0;i < n;i++){
22.             for(int j = 0;j < m;j++){
23.                 cout << dp[i][j] << " ";
24.             }
25.             cout << endl;
26.         }*/
27.         return ans;
28.     }
29. };
30. //tips 当然本题同样可以利用滚动数组的思想用一维数组来存储上一轮的数组 这里不多赘述

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。