列公子

用户名：lielielie

访问量：8859

签　名：

等　　级
排　　名	1615
经　　验	2513
参赛次数	0
文章发表	20
年　　龄	0
在职情况	学生
学　　校	哈尔滨工程大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法训练VIP-水仙花-题解(C++代码)
浏览：136

蓝桥杯 FBI树 DFS
浏览：282

蓝桥杯分苹果树状数组
浏览：204

你可能喜欢

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

蓝桥杯真题- 地宫取宝动态规划 / 记忆化搜索 (C++)

　　作者: 列公子　　　　发表时间：2020-02-16 16:07:55 浏览：1567　|　评论：1　

原题链接：蓝桥杯2014年第五届真题-地宫取宝

# [蓝桥杯真题] 地宫取宝 动态规划 / 记忆化搜索

## 1. 问题描述

基本可视作**搜索**的问题，但 **DFS 会超时**。

## 2. 动态规划法

### 2.1 最优值的定义及递归关系
#### 2.1.1 定义

```dp[x][y][num][maxValue]``` 为走到坐标```(x, y)```时, 不同行走方案总数的**最优值**(最大值), ```num```为背包中的物品总数, ```maxValue```为背包单个物品最大的价值。
此时未装入```(x, y)```处的物品。

#### 2.1.2 递归关系

1. 若装入```(x, y)``` 处的物品, 应先满足条件 ```c < C[x][y] && k > 0```, ```C```为物品价值数组。
```cpp
if (c < C[x][y] && k > 0){
	// 该点左方和上方
	int t1 = dp[x-1][y][num - 1][ C[x][y] ] + dp[x][y - 1][num - 1][ C[x][y] ];
	}
```
2. 不装入```(x, y)```处的物品
```cpp
// 该点左方和上方
int t2 = dp[x-1][y][num][maxValue] + dp[x][y-1][num][maxValue];
```
该点的最优值即为上述两种情况的最优值之和, 即:
```cpp
dp[x][y][num][maxValue] = (t1 + t2);    // 还应模那个大数
```

#### 2.1.3 边界值
```cpp
dp[1][1][0][maxValue] = 0;

// dp[1][1][1][]
```
### 2.2 完整代码 (AC)
最终结果为 ```dp[N][M][K][12]```
```cpp
// 蓝桥杯真题 地宫取宝
// 动态规划法
#include <cstdio>
const int maxn = 52;
const int maxnC = 13;
const int Q = 1000000007;   // 取模基数

int dp[maxn][maxn][maxnC][maxnC];     // 动态规划 dp[x][y][num][maxValue]
int C[maxn][maxn];      // 物品价值
int N, M, K;

int solve(){       // 迭代地动态规划
    for (int i = 1; i <= N; i++){       // x 坐标
        for (int j = 1; j <= M; j++){   // y 坐标
            for (int k = 0; k <= K; k++){   // 背包内物品总数
                for (int c = 0; c < maxnC; c++){      // 背包内单个物品的最大价值
                    if (i == 1 && j == 1){
                        if (k == 0 || (k == 1 && c > C[i][j]))
                            dp[i][j][k][c] = 1;
                        continue;
                    }

int t1 = 0, t2 = 0;
                    // 装当前物品
                    if (k > 0 && C[i][j] < c)
                        t1 = (dp[i][j-1][k-1][C[i][j]] + dp[i-1][j][k-1][C[i][j]]) % Q;
                    // 不装当前物品
                    t2 = (dp[i][j-1][k][c] + dp[i-1][j][k][c]) % Q;
                    dp[i][j][k][c] = (t1 + t2) % Q;
                }
            }
        }
    }
    return dp[N][M][K][maxnC-1];
}

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]);

printf("%d", solve());
    return 0;
}

```

## 3. 记忆化搜索

### 3.1 基本思想
基本框架与```DFS``` 一致, 搜索中**保存子问题的值**, 在搜索过程中若**子问题的最优值已存在**, 直接使用而避免重复搜索。

### 3.2 完整代码 (AC)
```cpp
//
// 蓝桥杯题库 真题 地宫寻宝
// 记忆化搜索
#include <cstdio>
#include <cstring>
typedef long long LL;
using namespace std;
const int maxn = 51;
const LL Q = 1000000007;    // 基数
int K, N, M;    // 个数, 行数, 列数
int G[maxn][maxn];
// 记忆化搜索
LL dp[maxn][maxn][maxn][maxn];

// 方向变更
int xx[2] = {1, 0};
int yy[2] = {0, 1};

// 记忆化搜索, 因为物品价值可能为0, 所以 maxValue 初始值为 -1, maxValue + 1 就是基于此
LL dfsMem(int x, int y, int num, int maxValue){
    if (dp[x][y][num][maxValue + 1] != -1){     // 已有结果
        return dp[x][y][num][maxValue + 1];
    }

if (x == N-1 && y == M-1){
       if (num == K || (num == K-1 && G[x][y] > maxValue)){
           return dp[x][y][num][maxValue + 1] = 1;     // 记录
       }
    }

LL s = 0;
    for (int i = 0; i < 2; i++){        // 遍历下方和右方
        int cx = x + xx[i], cy = y + yy[i];
        if (cx < N && cy < M){
            if (maxValue < G[x][y] && num < K)
                s += dfsMem(cx, cy, num+1, G[x][y]) % Q;
            s += dfsMem(cx, cy, num, maxValue) % Q;
        }
    }

return dp[x][y][num][maxValue + 1] = s % Q;
}

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", &G[i][j]);
    }
    memset(dp, -1, sizeof(dp));
    dfsMem(0, 0, 0, -1);

printf("%lld", dp[0][0][0][0]);
    return 0;
}
```

0.0分

12 人评分

C语言网强势推出「真C语言」普惠学习计划，依托C语言网强大的技术与丰富的资源支撑，让你一次性学会C语言从此告别“假C语言”，“只会理论”，“写不出代码”等问题，以含金量和学习效果勇敢挑战同类辅导！点击学习

　　评论区

hui

大哥，记忆化搜索不是动态规划？

2020-07-21 12:18:59

列公子

TA的其他文章

你可能喜欢

C语言训练-列出最简真分数序列* （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

C语言训练-斐波纳契数列（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

蓝桥杯真题- 地宫取宝动态规划 / 记忆化搜索 (C++)

评论区

精彩推荐

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

A+B for Input-Output Practice (V) （C++代码）

十->二进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

WU-小九九（C++代码）

列公子

TA的其他文章

你可能喜欢

C语言训练-列出最简真分数序列* （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

C语言训练-斐波纳契数列 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码） 用函数传参的方法

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

蓝桥杯真题- 地宫取宝 动态规划 / 记忆化搜索 (C++)

评论区

精彩推荐

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

A+B for Input-Output Practice (V) （C++代码）

十->二进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

WU-小九九 （C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

C语言训练-斐波纳契数列（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

蓝桥杯真题- 地宫取宝动态规划 / 记忆化搜索 (C++)

　　评论区

十->二进制转换（C语言代码）

WU-小九九（C++代码）