1. 笔试
1.1 题目
有16种状态码分别是1-16，本来应该记为{1, 1, 1, 3}，但是由于粗心记为{1113}，题目：求出给定的输入如{1113}能够构成不同状态码的个数。{1113}可以构成{1, 1, 1, 3}, {11, 1, 3}, {1, 11, 3}, {1, 1, 13}, {11, 13}这5种状态码组合，因此输出5。
输入
4 // 第一行表示4个输入
1 1 1 3 // 第二行表示4个输入的值
输出
5
1.2 思路分析
此题类似力扣91题 解码方法https://leetcode-cn.com/problems/decode-ways/
1. 分析合法的数值规律
合法的状态为1-16，
即一个状态要么是1-9的任意一个数；
要么是十位数只能是1，个位数为0~6的任意一个数。
2. 组合方式
本题共有2种组合方式，
假设对于前n-1个数，他们组合后记为
, 简称为Y，
那么对于第n个数x来说，可能的组合为Y,x 或者 Yx：
1）Y, x代表x为个位数的状态，x取1~9中的任意一个均可以，此处x加在前n-1个数的组合后面，
2）Yx表示
, 即第n-1个数y与第n个数x结合成一个状态yx，此处y只能为1，x只能为0~6, 此处的yx相当于添加在前n-2个数的组合后面。
3. 算法分析—动态规划
定义一个数组dp[i]；
含义：dp[i]表示截止到输入的第i个数字，所能构成的组合数
转移方程：根据1，2中的分析，可知，对于第i个数值，可能存在2种组合情况，
1）假设2种组合情况都能满足
那么dp[i] = dp[i-1] + dp[i-2] // 其中dp[i-1]表示Y,x dp[i-2]表示Yx情况的组合数
2）假设只能满足Y,x
那么dp[i] = dp[i-1]
3) 假设只能满足Yx
那么dp[i] = dp[i-2]
初始状态： dp[0]=1, dp[1]=1，且dp从2开始遍历 出于考虑dp[2]=dp[1]+dp[0]=2
其他特殊情况：输入为空、输入的第一个数为0
1.3 代码实现
#include <iostream>
using namespace std;int numDecode(vector<int> v)
{int n = v.size();if (n == 0) return 0;if (n == 1) return 1;int pre = v[0]; // 记录前一个数字if (!pre) return 0;vector<int>dp(n + 1, 1); // dp[i]表示到第i个数字的解码数量for (int i = 2; i <= n; ++i){int cur = v[i - 1];if ((pre == 0 || pre > 1) && cur == 0) return 0;if (pre == 1 && cur <= 6) // Y,X YX{if (cur != 0) // 可以Y,X{dp[i] = dp[i - 1] + dp[i - 2]; }else // 不能 Y,X{dp[i] = dp[i - 2];}}else // Y, X{dp[i] = dp[i - 1];}pre = cur;}return dp[n];
}int main()
{int n;cin >> n;vector<int> v(n, 0);for (int i = 0; i < n; ++i)cin >> v[i];cout << numDecode(v) << endl;return 0;
}
