大众点评笔试题最后两题题解

问题1：

这是一道动态规划的问题，状态转移方程为
dp[i] = dp[i-3] + dp[i-1] , i>= 3(i<3时dp[i]=1,仅仅有1种情况)
我这里直接开了一个dp数组解决问题。在init方法中进行了初始化。
另外，考虑到为了方便測试，我用了一个递归函数dfs(m,n,str)来进行对全部情况的输出。详细见代码：dfs函数的功能就是输出全部的可行方案。
如：当我输入5的时候，输出：
4
全部方案：
11111
211
121
112
同一时候我设定了数n的范围，当n<0时或n大于我设定的范围时，会提示出错。
以下是C++代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int maxn = 1010;
int dp[maxn];
void init() {
    dp[0] = dp[1] = dp[2] = 1;
    for(int i=3;i<maxn;i++) dp[i] = dp[i-1] + dp[i-3];
}
void dfs(int m,int n,string str) {
    if(m == 0) {
        cout << str << endl;
        return;
    }
    if(m >= 1)
        dfs(m-1 , n , "1"+str);
    if(m >= 3)
        dfs(m-3 , n , "2"+str);
    return;
}
int main() {
    int n;
    init();
    while(scanf("%d" , &n) != EOF) {
        if(n < 0) {
            puts("这段路的长度不能为负数！\n");
            continue;
        }
        if(n >= 1010) {
            puts("我这里设定的最大长度是1009,假设须要改变长度，请联系相关人员！");
            continue;
        }
        int ans = dp[n];
        printf("%d\n" , ans);
        printf("全部方案：\n");
        dfs(n , n , "");
    }
    return 0;
}

首先通过代码得到二进制数：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
void get(int n) {
    if(n == 0) return;
    get(n/2);printf("%d" , n%2);
}
int main() {
    get(3593);
    return 0;
}

2）至少须要开6个。
第一秒先推断3593的前6个二进制位；
第二秒推断3593的后6个二进制位。
方法同1）。

注：2）的解答不一定对。