当前位置:网站首页>2328. 网格图中递增路径的数目(记忆化搜索)
2328. 网格图中递增路径的数目(记忆化搜索)
2022-07-06 04:11:00 【Harris-H】
2328. 网格图中递增路径的数目(记忆化搜索)
原理矩阵的四周扩散,也可以记忆化dp。
时间复杂度: O ( n m ) O(nm) O(nm)
class Solution {
public:
int countPaths(vector<vector<int>>& a) {
int n =a.size(),m=a[0].size();
vector<vector<int> >f(n,vector<int>(m,-1));
int d[4][2] ={
0,1,0,-1,1,0,-1,0};
const int mod = 1e9+7;
function<int(int,int)> dfs = [&](int x,int y){
if(~f[x][y]) return f[x][y];
int ans = 1;
for(int i=0;i<4;i++){
int nx = x+d[i][0],ny=y+d[i][1];
if(nx>=0 && nx<n && ny>=0 && ny<m && a[nx][ny] >a[x][y]){
ans=(ans+dfs(nx,ny))%mod;
}
}
return f[x][y] =ans;
};
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++) ans=(ans+dfs(i,j))%mod;
return ans;
}
};
边栏推荐
- One question per day (Mathematics)
- Cf464e the classic problem [shortest path, chairman tree]
- 【按鍵消抖】基於FPGA的按鍵消抖模塊開發
- Yyds dry goods inventory web components series (VII) -- life cycle of custom components
- 深入浅出node模板解析错误escape is not a function
- ESP32_ FreeRTOS_ Arduino_ 1_ Create task
- MySql数据库root账户无法远程登陆解决办法
- [Key shake elimination] development of key shake elimination module based on FPGA
- Path of class file generated by idea compiling JSP page
- 2/12 didn't learn anything
猜你喜欢
Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
Security xxE vulnerability recurrence (XXe Lab)
Custom event of C (31)
Record the pit of NETCORE's memory surge
Chinese brand hybrid technology: there is no best technical route, only better products
【leetcode】1189. Maximum number of "balloons"
The Research Report "2022 RPA supplier strength matrix analysis of China's banking industry" was officially launched
Lombok原理和同时使⽤@Data和@Builder 的坑
【PSO】基于PSO粒子群优化的物料点货物运输成本最低值计算matlab仿真,包括运输费用、代理人转换费用、运输方式转化费用和时间惩罚费用
关于进程、线程、协程、同步、异步、阻塞、非阻塞、并发、并行、串行的理解
随机推荐
Python book learning notes - Chapter 09 section 01 create and use classes
【PSO】基于PSO粒子群优化的物料点货物运输成本最低值计算matlab仿真,包括运输费用、代理人转换费用、运输方式转化费用和时间惩罚费用
Global and Chinese markets for medical gas manifolds 2022-2028: Research Report on technology, participants, trends, market size and share
Deep learning framework installation (tensorflow & pytorch & paddlepaddle)
Solution to the problem that the root account of MySQL database cannot be logged in remotely
MySQL learning record 13 database connection pool, pooling technology, DBCP, c3p0
Solution of storage bar code management system in food industry
math_ Derivative function derivation of limit & differential & derivative & derivative / logarithmic function (derivative definition limit method) / derivative formula derivation of exponential functi
lora网关以太网传输
Lambda expression learning
题解:《单词覆盖还原》、《最长连号》、《小玉买文具》、《小玉家的电费》
Global and Chinese market of aircraft anti icing and rain protection systems 2022-2028: Research Report on technology, participants, trends, market size and share
Comprehensive ability evaluation system
查询mysql数据库中各表记录数大小
Stable Huawei micro certification, stable Huawei cloud database service practice
E. Best Pair
PTA tiantisai l1-078 teacher Ji's return (15 points) detailed explanation
P2648 make money
AcWing 243. A simple integer problem 2 (tree array interval modification interval query)
Database, relational database and NoSQL non relational database