列公子

用户名：lielielie

访问量：9590

签　名：

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

　　自我简介：

TA的其他文章

蓝桥杯算法提高- 和最大子序列动态规划 C++
浏览：327

蓝桥杯算法提高VIP-种树动态规划 / DFS (C++)
浏览：787

蓝桥杯棋盘多项式 DFS (C++)
浏览：529

你可能喜欢

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

　　作者: 列公子　　　　发表时间：2020-02-16 16:07:55 浏览：1900　|　评论：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分

14 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

hui

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

2020-07-21 12:18:59

列公子

TA的其他文章

你可能喜欢

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

C二级辅导-同因查找（C语言代码）

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

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

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

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

评论区

精彩推荐

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

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

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

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

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

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

数列排序（C语言代码）

九宫重排（C++代码）

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

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

列公子

TA的其他文章

你可能喜欢

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

C二级辅导-同因查找 （C语言代码）

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

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

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

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

评论区

精彩推荐

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

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

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

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

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

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

数列排序 （C语言代码）

九宫重排 （C++代码）

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

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

C二级辅导-同因查找（C语言代码）

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

　　评论区

数列排序（C语言代码）

九宫重排（C++代码）