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不一定可以用记忆化搜索去实现
（记忆化搜索是递归的实现，递归可以转换成更详细的迭代去覆盖，但是迭代不一定能找到合适的递归去覆盖所有的情况）