dfs求最小值：
1. 记一个全局最小值
每次dfs结束，并且找到合法解的时候，更新全局最小值
2. 迭代加深
一定程度上相当于bfs，首先深度优先搜索到第depth层，如果没有搜索成功，再从头开始深度优先搜索到第depth+1层
时间效率只比bfs慢一点，但是空间复杂度远小于bfs，并且更方便剪枝
dfs+全局最小值
#include <iostream>
#include <cstdio>
#include <climits>
using namespace std;
int n;
int ans;
const int N = 55;
int a[N], up[N], down[N];
void dfs(int u, int su, int sd) // 传入参数：当前讨论的a[u]，最长上升子序列长度，最长下降子序列长度
{
if(su + sd >= ans) return; // 如果到这里已经满足该条件，说明之后的所有情况都不会再对ans产生更新效果（取min），剪枝
if(u == n)
{
ans = su + sd; // 结合第一个return条件，此处等价于ans = min(ans, su + sd);
return;
}
// Case1: put the current u into the increasing subsequence
int l = 0, r = su;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(up[mid] <= a[u]) l = mid;
else r = mid - 1;
}
int t = up[r + 1];
up[r + 1] = a[u];
if(r == su) dfs(u + 1, su + 1, sd);
else dfs(u + 1, su, sd);
up[r + 1] = t; // 恢复现场
// Case2: put the current u into the decreasing subsequence
l = 0, r = sd;
while(l < r)
{
int mid = l + r + 1>> 1;
if(down[mid] >= a[u]) l = mid;
else r = mid - 1;
}
t = down[r + 1];
down[r + 1] = a[u];
if(r == sd) dfs(u + 1, su, sd + 1);
else dfs(u + 1, su, sd);
down[r + 1] = t; // 恢复现场
}
int main()
{
// 初始化up和down数组，保证所有的数据都能够找到插入的地方
down[0] = INT_MAX; // 有无穷大作上界
// up[0] = 0 ，有0作下界
while(scanf("%d", &n), n)
{
for (int i = 0; i < n; i ++) scanf("%d", a + i);
ans = n;
dfs(0, 0, 0);
printf("%d\n", ans);
}
return 0;
}
dfs+迭代加深
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 55;
int n;
int a[N], up[N], down[N];
// up, down 数组分别存储的是当前depth的搜索条件下所有已经创建的上升子序列和下降子序列的结尾元素
// 区别于贪心法求最长上升子序列中的up和down数组
bool dfs(int depth, int u, int su, int sd)
{
if(su + sd > depth) return false; // 如果已经不满足depth条件，那就返回false，剪枝
if(u == n) return true; // 如果已经放完了所有元素，就返回true，是个合法的满足su+sd<=depth的方案
// insert the recent a[u] into an increasing subsequence
bool find = false;
for (int i = 0; i < su; i ++)
if(up[i] < a[u]) // 找到一个可以放置元素a[u]的地方，就放进去
{
find = true;
int t = up[i];
up[i] = a[u];
if(dfs(depth, u + 1, su, sd)) return true;
up[i] = t;
break;
}
if(!find){ // 如果没有找到，即a[u]比所有现有序列的末尾元素都要小或等，就单独再创建一个序列
up[su] = a[u];
if(dfs(depth, u + 1, su + 1, sd)) return true;
}
// 如果放在increaseing序列中已经满足情况，那么就直接返回true，不会再继续尝试下一个分支
//（相当于bfs中在某一层搜到的第一个满足条件的节点）
// insert the current a[u] into a decreasing subsequence
find = false;
for (int i = 0; i < sd; i ++)
if(down[i] > a[u])
{
find = true;
int t = down[i];
down[i] = a[u];
if(dfs(depth, u + 1, su, sd)) return true;
down[i] = t;
break;
}
if(!find){
down[sd] = a[u];
if(dfs(depth, u + 1, su, sd + 1)) return true;
}
return false;
}
int main()
{
while(scanf("%d", &n), n)
{
for (int i = 0; i < n; i ++) scanf("%d", a + i);
int depth = 0; // 枚举答案
while(!dfs(depth, 0, 0, 0)) depth ++; //如果可以满足su+sd<=depth，说明已经是可行解，就直接输出depth
cout << depth << endl;
}
return 0;
}
dfs+迭代加深+二分查找
根据前一个up数组和down数组的含义，很容易发现：
up数组是单调递减（不严格）的，而down数组是不严格单调递增的
所以顺序搜索一个可以放置a[u]的朴素查找就可以替换成二分查找
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 55;
int n;
int a[N], up[N], down[N];
// up, down 数组分别存储的是当前depth的搜索条件下所有已经创建的上升子序列和下降子序列的结尾元素
// 区别于贪心法求最长上升子序列中的up和down数组
bool dfs(int depth, int u, int su, int sd)
{
if(su + sd > depth) return false; // 如果已经不满足depth条件，那就返回false，剪枝
if(u == n) return true; // 如果已经放完了所有元素，就返回true，是个合法的满足su+sd<=depth的方案
// insert the recent a[u] into an increasing subsequence
int l = 0, r = su;
while(l < r) // 二分查找最大的小于a[u]的结尾值
{
int mid = l + r >> 1;
if(up[mid] >= a[u]) l = mid + 1;
else r = mid;
}
if(r != su){ // 如果找到了，就用a[u]更新，然后继续dfs
int t = up[r];
up[r] = a[u];
if(dfs(depth, u + 1, su, sd)) return true;
up[r] = t; // 恢复现场
}
else{ // 如果没找到，就再开一个上升序列（目前只有一个值a[u]）
up[r] = a[u];
if(dfs(depth, u + 1, su + 1, sd)) return true;
}
// insert the current a[u] into a decreasing subsequence
l = 0, r = sd;
while(l < r)
{
int mid = l + r >> 1;
if(down[mid] <= a[u]) l = mid + 1;
else r = mid;
}
if(r != sd){
int t = down[r];
down[r] = a[u];
if(dfs(depth, u + 1, su, sd)) return true;
down[r] = t;
}
else{
down[r] = a[u];
if(dfs(depth, u + 1, su, sd + 1)) return true;
}
return false;
}
int main()
{
while(scanf("%d", &n), n)
{
for (int i = 0; i < n; i ++) scanf("%d", a + i);
int depth = 0;
while(!dfs(depth, 0, 0, 0)) depth ++;
cout << depth << endl;
}
return 0;
}
