当前位置:网站首页>2328. Number of incremental paths in the grid graph (memory search)
2328. Number of incremental paths in the grid graph (memory search)
2022-07-06 04:15:00 【Harris-H】
2328. The number of incremental paths in the grid graph ( Memory search )
Diffusion around the principle matrix , It can also be memorized dp.
Time complexity : 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;
}
};
边栏推荐
- [Zhao Yuqiang] deploy kubernetes cluster with binary package
- 自动化测试的好处
- 《2022年中国银行业RPA供应商实力矩阵分析》研究报告正式启动
- MySQL master-slave replication
- Global and Chinese markets for MRI safe implants 2022-2028: technology, participants, trends, market size and share Research Report
- 20、 EEPROM memory (AT24C02) (similar to AD)
- VPP performance test
- 2/12 didn't learn anything
- Practical development of member management applet 06 introduction to life cycle function and user-defined method
- Data processing methods - smote series and adasyn
猜你喜欢
Viewing and verifying backup sets using dmrman
[PSO] Based on PSO particle swarm optimization, matlab simulation of the calculation of the lowest transportation cost of goods at material points, including transportation costs, agent conversion cos
lora网关以太网传输
Redis (replicate dictionary server) cache
Query the number and size of records in each table in MySQL database
自动化测试的好处
Esp32 (based on Arduino) connects the mqtt server of emqx to upload information and command control
1291_ Add timestamp function in xshell log
Web components series (VII) -- life cycle of custom components
In depth MySQL transactions, stored procedures and triggers
随机推荐
About some basic DP -- those things about coins (the basic introduction of DP)
Overturn your cognition? The nature of get and post requests
Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
SSTI template injection explanation and real problem practice
Lombok原理和同时使⽤@Data和@Builder 的坑
10個 Istio 流量管理 最常用的例子,你知道幾個?
判断当天是当月的第几周
The global and Chinese market of negative pressure wound therapy unit (npwtu) 2022-2028: Research Report on technology, participants, trends, market size and share
Chinese brand hybrid technology: there is no best technical route, only better products
Interface idempotency
Tips for using dm8huge table
Global and Chinese markets for endoscopic drying storage cabinets 2022-2028: Research Report on technology, participants, trends, market size and share
User datagram protocol UDP
During pycharm debugging, the view is read only and pause the process to use the command line appear on the console input
10个 Istio 流量管理 最常用的例子,你知道几个?
Ipv4中的A 、B、C类网络及子网掩码
How does technology have the ability to solve problems perfectly
Yyds dry goods inventory web components series (VII) -- life cycle of custom components
Stable Huawei micro certification, stable Huawei cloud database service practice
Redis (replicate dictionary server) cache