记忆化搜索
暴力搜索的途中会经过很多重复的结点,这导致的普通dfs的超时,因此我们可以用一个备忘录来记录每个状态是否求解过了,当重复搜索到同一状态时,我们就可以直接返回而不必重复相同的递归操作了,这样就大量节省时间复杂度。
备忘录的定义:
根据题意,我们需要知道4个状态,即当前的位置(i, j),以及当前拿了多少件宝物和最近拿的宝物的价值c
因此备忘录是一个四维数组:memo[i][j][k][c]
根据要求,memo数组的值应该表示从(i, j, k, c)这个状态走到终点的合法方案数
细节问题:由于本题中宝物的价值可能为0,因此为了实现方便,我们给每个宝物的价值都加上1的偏移量,这样我们就可以用c = 0表示当前一个宝物都没取的情况了,对于memo数组的初始化,我们不能将其初始化为0,因为memo为0也属于一种合法方案数,因此我们将其初始为-1
起点状态:在(1, 1)位置,选了0件宝物,上一件宝物的价值为0(即未选)
结果:在实现完记忆化搜索之后,我们的结果就是从起点状态到终点的合法方案数memo[1][1][0][0]
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 55, M = 15, mod = 1e9 + 7;
int w[N][N];
int memo[N][N][M][M]; //memo[i, j, k, c]记录当状态为(i, j, k, c)时,继续走直到终点的合法方案数
int n, m, K, ans;
int dfs(int i, int j, int k, int c){
if(memo[i][j][k][c] != -1)
return memo[i][j][k][c];
if(i == n && j == m){
if(k == K || (k == K - 1 && w[i][j] > c))
return 1;
else return 0;
}
int sum = 0; //记录当前状态走到终点的合法方案数
if(i + 1 <= n){
if(w[i][j] > c) sum = (sum + dfs(i + 1, j, k + 1, w[i][j])) % mod;
sum = (sum + dfs(i + 1, j, k, c)) % mod;
}
if(j + 1 <= m){
if(w[i][j] > c) sum = (sum + dfs(i, j + 1, k + 1, w[i][j])) % mod;
sum = (sum + dfs(i, j + 1, k, c)) % mod;
}
return memo[i][j][k][c] = sum % mod;
}
int main(){
scanf("%d %d %d", &n, &m, &K);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &w[i][j]);
w[i][j]++;
}
}
memset(memo, -1, sizeof(memo)); //memo[i, j, k, c]为0也是一种合法方案,因此我们的memo数组必须初始化为-1
dfs(1, 1, 0, 0);
printf("%d\n", memo[1][1][0][0]);
return 0;
}
动态规划
见注释
C++ 代码
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 55, M = 15, mod = 1000000007;
int C[N][N];
int f[N][N][M][M];
//状态表示:f[i, j, k, c]表示走到(i, j), 手中恰好有k件宝物且最近取得的宝物价值为c的方案数
//递推方程:
//(1)不选(i, j)处的宝物,f[i, j, k, c] = f[i - 1, j, k, c] + f[i, j - 1, k, c]
//(2)选(i, j)处的宝物,在 c = C[i][j], t < c的范围中 f[i, j, k, c] += f[i - 1, j, k - 1, t] + f[i, j - 1, k - 1, t]
int n, m, K;
int main(){
scanf("%d %d %d", &n, &m, &K);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &C[i][j]);
C[i][j]++;
}
}
f[1][1][1][C[1][1]] = 1; //取第一个物品
f[1][1][0][0] = 1; //不取第一个物品
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
for(int k = 0; k <= K; k++){
for(int c = 0; c <= 13; c++){
f[i][j][k][c] = ((f[i][j][k][c] + f[i - 1][j][k][c]) % mod + f[i][j - 1][k][c]) % mod;
if(k > 0 && C[i][j] == c){
for(int t = 0; t < C[i][j]; t++)
f[i][j][k][c] = ((f[i][j][k][c] + f[i - 1][j][k - 1][t]) % mod + f[i][j - 1][k - 1][t]) % mod;
}
}
}
}
}
int ans = 0;
for(int i = 0; i <= 13; i++) ans = (ans + f[n][m][K][i]) % mod;
printf("%d\n", ans);
return 0;
}