Algorithm8.5 搜索思维题 & 数字题目类型整合
[TOC]
搜索思维题
特点:可以用搜索,但是可能会T或者需要剪枝过多
- 特殊地图(某方向固定长度)起点到终点 + 特殊走法:考虑按照特殊方向进行模拟
- 特殊走法(不允许往某个方向走):考虑直接全盘dp
特殊地图起点到终点-特殊走法:
- 两行地图
- 特殊走法,只往一边走更优
特殊走法:
- 某单个方向不能走
// 搜索
int cnt, ans;
void dfs(int l) {
if (l == n) { if (cnt == m) ans++;return;}
for (int i = 0; i <= a[l+1]; ++i) { cnt+=i;dfs(l+1);cnt-=i; }
}
可以看到其实cnt,(本来是一个全局变量)也可以写成递归的一个依据,因为进入之前与之后有相反操作,因此优化
int ans;
void dfs(int l, int cnt) {
if (l == n) { if (cnt == m) ans++;return; }
for (int i = 0; i <= a[l+1]; ++i) dfs(l+1, cnt+i);
}
记忆化搜索
https://www.luogu.com.cn/problem/P1464
题目大意:纯粹的重复递归调用,极限的话20 * 20 * 20次不同的计算要被一直算,如果可以记录下来,那么这么多次运算只需要算一遍。
1、用dp来记录下来每次的递归结果,也就是return之前先给dp附上值。return dp=w();
2、注意return的时候,看看边界条件,特判条件放在前面先return;递归条件放后面return
#include <iostream>
using namespace std;
#define maxn 25
typedef long long ll;
ll ta, tb, tc, dp[maxn][maxn][maxn];
ll dfs(int a, int b, int c) {
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return dfs(20, 20, 20);
if (dp[a][b][c]) return dp[a][b][c];
if (a < b && b < c) return dp[a][b][c] = dfs(a, b, c-1) + dfs(a, b-1, c-1) - dfs(a, b-1, c);
else return dp[a][b][c] = dfs(a-1, b, c) + dfs(a-1, b-1, c) + dfs(a-1, b, c-1) - dfs(a-1, b-1, c-1);
}
int main() {
while (scanf("%lld%lld%lld", &ta, &tb, &tc) && !(ta==-1 && tb==-1 && tc==-1))
printf("w(%lld, %lld, %lld) = %lld\n", ta, tb, tc, dfs(ta, tb, tc));
return 0;
}
记忆化搜索转化为dp
记忆化搜索都可以转化为dp,但是dp不一定可以用记忆化搜索去实现
(记忆化搜索是递归的实现,递归可以转换成更详细的迭代去覆盖,但是迭代不一定能找到合适的递归去覆盖所有的情况)