1457972626
不得不说的暴力的dfs深度搜索法，临时抱佛脚，过几天是蓝桥杯省赛，花一两天时间练习dfs
题目不求多练，主要是靠理解。
废话不说，列几道刚水过的题
题目描述
标题：李白打酒
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。
解题思路
题目一览而过，最直接的就是dfs
代码实现
public class LiBaiHeJiu {
private static int count = 0;
static char[] s = new char[20];
static int f(int d, int h, int j) {
if (d > 0)
f(d - 1, h, j * 2);
if (h > 0)
f(d, h - 1, j - 1);
if (d == 0 && h == 1 && j == 1)
count++;
return count;
}
static void m(int d, int h, int j) {
if (d < 0 || h < 0 || j < 0)
return;
if (d == 0 && h == 1 && j == 1) {
System.out.println(s.toString());
count++;
}
s[d + h - 1] = 'a';
f(d - 1, h, j * 2);
s[d + h - 1] = 'b';
f(d, h - 1, j - 1);
}
public static void main(String agrs[]) {
m(5, 10, 2);
System.out.println(count);
}}
题目描述
题目标题: 第39级台阶
小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
请你利用计算机的优势，帮助小明寻找答案。
要求提交的是一个整数。
注意：不要提交解答过程，或其它的辅助说明文字。
题目思路
一看题目可以选择递归，可以使用dfs，下面是使用dfs解法
代码实现
/**
39级阶梯问题
@author Ape
/
public class JT {static int count = 0;
static void w(int n, int step) {
if (n < 0) return; if (n == 0 && step % 2 == 0) { count++; return; } w(n - 1, step + 1); w(n - 2, step + 1);}
public static void main(String agrs[]) {
w(39, 0); System.out.println(count);}
}