织梦网站地图调用全站文章,注册代理公司流程及费用,郑州seo外包阿亮,西安二手房题目如下
数据范围
本题使用常规动态规划就行#xff0c;不过要注意由于有三个转移的方向#xff0c;所以我们对dp数组的遍历应该是从上到下 从左到右即按列优先遍历。通过代码
class Solution {
public:int maxMoves(vectorvectorint grid) {int …题目如下
数据范围
本题使用常规动态规划就行不过要注意由于有三个转移的方向所以我们对dp数组的遍历应该是从上到下 从左到右即按列优先遍历。通过代码
class Solution {
public:int maxMoves(vectorvectorint grid) {int n grid.size();int m grid[0].size();vectorvectorint dp(n,vectorint(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 当然本题同样可以利用滚动数组的思想用一维数组来存储上一轮的数组 这里不多赘述
