一道有趣的编程题

[rwdy2008]

最近遇到这样一个题，觉得挺有意思，V 友们一起讨论下撒

题目如下： N 个面包，分两种吃法，一次吃 1 个或者一次吃 2 个，求所有吃法的序列组合并打印。

PS：是所有的序列组合，不是总数。不限语言

[troycheng]

吃到第 N 个面包时的状态，前驱状态可以是从第 N-2 个吃两个，也可以从 N-1 个吃一个
N=1 的时候，只有一种吃法
N=2 的时候，有两种吃法
序列的话，加个变量记一下结果即可

[bolide2005]

有啥意思啊……这不就是爬楼梯问题吗，换个马甲

[vegito2002]

如果一次可以吃 1..N-1 个, 打印所有序列; 就是一个拆分加法求和的问题

[oceanTu]

问题基因是兔子数列
如果要列举可以做子问题拆分 question(N)状态下吃一个和吃两个，得到两个子问题 question(N-1), question(N-2)。
子问题状态会重复，可以保存状态优化。
脑子里 YY 了一下，解的结构像是巨大的二叉树，节点是子问题，两个枝是吃一个，吃两个。任意从根到叶子的路径是一种吃法。

[ai277014717]

这不是动态规划么。

[ballshapesdsd]

毫无难度

[cdlixucd]

@ballshapesdsd talk is cheap,show me the code

[qiuyk]

呃 不就是多记录个状态么 动态规划完了还原解法不就好了....

[LenonZeng]

把第 n 步和第 n-1 步的情况搞清楚 得到一个递推式子外加 0 个面包 1 个面包 2 个面包的初始情况 递归下

[daxingzhesun]

好像有个题叫走台阶,一次走一步或者两步,好像是 2 的 n 次方-1

[rwdy2008]

V 友们，觉得 so easy 的，展示出你们如大屌般强悍的最优代码啊

[Youen]

backtracking 吗

[daxingzhesun]

public int eat(int n) {
if (n == 1 && n == 0) {
return 1;
} else if (n == 2) {
return 2;
}else{
return eat(n-1)+eat(n-2);
}

}

[rwdy2008]

@daxingzhesun 题目是打印所有的序列，不是序列总数

[caixiangyu17]

def f(n):
if n == 1:
return ['1']
if n == 2:
return ['11', '2']
return list(set(list(set(map(lambda x: '1' + x, f(n - 1)))) +
list(set(map(lambda x: '2' + x, f(n - 2)))) +
list(set(map(lambda x: '11' + x, f(n - 2))))))
动态规划了解一下

[lhx2008]

楼上说动态规划的，真的有用到吗？

[hourann]

@lhx2008 哈哈哈，加个 lru_cache 就是了

[shilyx]

递归嘛，最简单，c++：
/*
*　 @file 　: TestNBread.cpp
*　 @author: slx
*　 @date 　: 2018-04-27 12:21:26.865
*　 @note 　: Generated by SlxTemplates
*/

#include <iostream>

using namespace std;

void dojob(int N, char buf[], int sum) {
　　 if (N - sum == 1) {
　　　　 cout << buf << 1 << endl;
　　} else if (N - sum == 2) {
　　　　 cout << buf << 2 << endl;
　　　　 cout << buf << 11 << endl;
　　} else {
　　　　 int len = strlen(buf);
　　　　 buf[len + 1] = 0;
　　　　 buf[len] = '1';
　　　　 dojob(N, buf, sum + 1);
　　　　 buf[len + 1] = 0;
　　　　 buf[len] = '2';
　　　　 dojob(N, buf, sum + 2);
　　}
}

void dojob(int N) {
　　 char *buf = (char *)malloc(N + 1);
　　 memset(buf, 0, N + 1);
　　 dojob(N, buf, 0);
　　 free(buf);
}

int main(int argc, char *argv[])
{
　　 dojob(7);
　　 return 0;
}
结果：
111112
1111111
111121
11122
111211
11212
112111
11221
12112
121111
12121
1222
12211
21112
211111
21121
2122
21211
2212
22111
2221
请按任意键继续. . .

[xuc]

https://leetcode-cn.com/problems/climbing-stairs/

[bolide2005]

用啥动态规划啊
f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)
联立可解