这个问题最明显的特征就是有规模，并且大规模版本的答案是和小规模版本的答案密切相关的，也就是已知李白(x, y, z)，我们马上就能知道李白(x+1, y, z+1)或者李白(x, y+1, 2z)的答案。 不知道到这里有没有人能想起菲波纳契数列和对应的经典计算机算法动态规划。动态规划是非常经典的空间换时间的算法，可以把这类问题 最笨拙的暴力递归算法瞬间改造成性能相当良好的算法。
int main() { int cnt=0; for (int i=0; i<1<<15; i++) { int k=2; int n=0; int x=i; int flag=1; for (int j=1; j<=15; j++) { if (x&1) k*=2; else k--; if (k==0&&x) { flag=0; break; } n+=x&1; x>>=1; } if ( n !=5 || (i & (1<<14)) || !flag || k != 0) continue; cnt++; } cout<
#include using namespace std; int count = 0; int path[ 20 ]; void dfs( int m, int n, int r, int c )//m 遇店的次数，n 遇花的次数 { if( m < 0 || n < 0 || r < 0 ) return ; if( m ==0 && n == 0 && r == 1 ) { path[ c ] = '\0'; cout << path << endl; count++; } path[ c ] = 'a'; dfs( m -1 , n, r * 2, c + 1 ); path[ c ] = 'b'; dfs( m, n - 1, r - 1 , c + 1 ); } int main() { dfs( 5, 9, 2, 0 ); cout << count << endl; return 0; }
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
henix的思路非常好，只是这一句“所以问题转化为把 8 拆成 5 个 2 的幂”略有问题，漏掉了类似12311的组合（即漏掉了可能＋3的情形）。
加3斗的情况会在如下情境中触发：当前酒为2斗时候，遇店加至4斗，遇花喝掉一斗，此时有3斗，再遇店加3斗。所以这个组合中3必须紧挨着2，在2的后面，相当于"23"捆绑在一起。此种情况下有C(4,1) = 4种。总答案为C(5,2)＋C(4,1)为14种。
每见一次花喝 1 斗，由于最开始有 2 斗，总共见了 10 次花，说明总共喝了 10 斗。所以因为遇见店而增加的酒为 8 斗。
所以问题转化为把 8 拆成 5 个 2 的幂，也就是考虑每次遇见店增加多少斗。有两种：
1 1 2 2 2
1 1 1 1 4
但是没有 2 直接出现 4 是不可能的，所以只有 1 1 2 2 2 是可行的。
所以问题转化为 1 1 2 2 2 这 5 个数有多少种排列方法，共 C(5,2) = 10 种。
这样的问题用枚举加剪枝的方式应该是可以接受的吧，下面我写的python代码：
貌似楼主用C++，那个路径可以stack实现。补充一下运行结果（共14种）：
哎……大家都各贴各的代码，也不说说重要的优化思路
翻了一下还几乎没在答案里找到靠谱的优化思路解说，如果这是我在面试的话这里的答案几乎没人到我心理预估60分……
为了方便描述，定义一下
李白(x, y, z)=> 还有x次花，y次店，z斗酒的答案先说不重要的吧，剪枝条件是可以比各位的答案更激进一些的，比如
z > x的时候玩命喝也喝不完了可以剪，同理z * (2 ^ y) < x的时候即使马上狂打酒也不够喝了可以剪。正文分隔线
这个问题最明显的特征就是有规模，并且大规模版本的答案是和小规模版本的答案密切相关的，也就是已知
李白(x, y, z)，我们马上就能知道李白(x+1, y, z+1)或者李白(x, y+1, 2z)的答案。不知道到这里有没有人能想起菲波纳契数列和对应的经典计算机算法动态规划。动态规划是非常经典的空间换时间的算法，可以把这类问题 最笨拙的暴力递归算法瞬间改造成性能相当良好的算法。
实际上，不用动态规划的话，这类问题的递归算法会很快随着规模的增长而崩溃,具体O多少还给算法老师了，反正肯定是逆天指数级的。动态规划以后基本可以降到多项式级别
最后给出我的实现，嗯，JS的
http://jsfiddle.net/e3Ns4/
_.memoize(fn, hasher)是underscore里的一个helper，作用是生成一个新的函数，调用时会先用haser计算一个hash，然后把结果缓存在这个hash里，下次相同hash值就不调用fn了，也就是动态规划。源代码我抄过来我想一个穷举的思路吧~其实不用很多步骤的~
首先要递归
开始2斗，5酒店，10花；
楼上都完整了...
提供优化条件吧
如果酒店完了，并且斗和花不等，就能退出；
如果斗大于花也能退出；
斗已经是0直接退出；
花是零，但没到15步也退出；
额...代码如下(python版)：
执行
w(2,5,10)结果14自己写不来，让某大神写的枚举代码：
让我来个haskell递归版的
给你一段更容易理解的代码，用递归做的：
自己先粗略的写了一下，刚调试了一下，还是有点问题，已经被他折磨了两个小时了，先休息会儿等会儿再来debug！
结果debug了好久，也没我想的那么简单，也没人提示，今天又花了半个小时左右的时间，终于找到了问题的所在！
更新版本,已通过测试：