#include <iostream> #include <cstdio> #include <cstdlib> #define mod 1000000007 using namespace std; int n,m,k,c; int mp[50][50]; void dfs(int x,int y,int max_,int cc) { if(x == n - 1 && y == m - 1) { c += cc == k || cc == k - 1 && mp[x][y] > max_; return; } if(x < n - 1) { if(cc < k && mp[x][y] > max_) dfs(x + 1,y,mp[x][y],cc + 1); dfs(x + 1,y,max_,cc); } if(y < m - 1) { if(cc < k && mp[x][y] > max_) dfs(x,y + 1,mp[x][y],cc + 1); dfs(x,y + 1,max_,cc); } } int main() { scanf("%d%d%d",&n,&m,&k); for(int i = 0;i < n;i ++) { for(int j = 0;j < m;j ++) { scanf("%d",&mp[i][j]); mp[i][j] ++; } } dfs(0,0,0,0); printf("%d",c); }
仔细想想，从某个点到结尾的路是确定那么几条的，因为只允许向右和下走嘛，我们可以记录每个点，对应某个最大值以及相应手中宝贝个数的方案数，这样前面的点访问到后面的点时就可以直接用存的方案数去进行匹配衔接。dfs有四个参数，坐标以及手中最大值和手中宝贝数，显然在点(x,y)它的状态与max_和cc有关，而这种状态来自前面的路径，也就是说只要前面的路径情况满足最大值时max_,且手中宝贝数时cc，且到了点(x,y)，而点(x,y)对此状态有存，就可以直接使用返回。
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #define mod 1000000007 using namespace std; int n,m,k; int mp[51][51]; int sta[51][51][14][14]; int dfs(int x,int y,int max_,int cc) { if(sta[x][y][max_][cc] != -1) return sta[x][y][max_][cc]; if(x == n - 1 && y == m - 1) { return sta[x][y][max_][cc] = (cc == k || cc == k - 1 && mp[x][y] > max_); } int sum = 0; if(x < n - 1) { if(cc < k && max_ < mp[x][y]) { sum = (sum + dfs(x + 1,y,mp[x][y],cc + 1)) % mod; } sum = (sum + dfs(x + 1,y,max_,cc)) % mod; } if(y < m - 1) { if(cc < k && max_ < mp[x][y]) { sum = (sum + dfs(x,y + 1,mp[x][y],cc + 1)) % mod; } sum = (sum + dfs(x,y + 1,max_,cc)) % mod; } return sta[x][y][max_][cc] = sum; } int main() { scanf("%d%d%d",&n,&m,&k); for(int i = 0;i < n;i ++) { for(int j = 0;j < m;j ++) { scanf("%d",&mp[i][j]); mp[i][j] ++;///避开0 } } memset(sta,-1,sizeof(sta)); dfs(0,0,0,0); printf("%d",sta[0][0][0][0]); }
原文：https://www.cnblogs.com/8023spz/p/10488667.html