【每日一题】「火」皇家烈焰
「火」皇家烈焰
https://ac.nowcoder.com/acm/problem/53683
题目
题目描述：帕秋莉掌握了一种火属性魔法
由于钟爱扫雷游戏，帕秋莉把自己图书馆前的走廊看作一个一维的扫雷地图，她制造了很多烈焰，排在这条走廊内
现在帕秋莉告诉你一部分烈焰的分布情况，请你告诉她可能的情况有多少种
对于一个格子，里面会有以下几种字符：
0：这个格子没有烈焰，且其左右两个格子均没有烈焰
1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰
2：这个格子没有烈焰，且其左右两个格子中均有烈焰
*：这个格子有烈焰
？：未告诉你本格情况
输入描述：
一个字符串
输出一行，一个整数表示答案，对1e9+7取模
解析
梳理题目意思，这就是一个一维扫雷。
这道题很清楚的可以看出来是一道dp，而且这么多情况还要分类讨论
- 所以还是先这个：动态规划最重要的就是递推。
动态规划：
- 这道题我相信大家一下就能看出来这是一个dp的题目。但是我却想不到该用一个什么样的dp。
- 我重复了很多遍的递推固然重要，但是我有一点没提过：就是dp数组的意义。
- 这道题我完全没有数组定义的思路，在看了邓老师的题解之后我感觉有了一些发现：数组应该根据所求数据的相关性进行确定。
- 本道题我们将dp数组定义为：dp[i][0/1][0/1]。（dp[下标位置][本位是否为烈焰][下一位是否为烈焰] = 到达下标位置之前的种类数）
- 那么本憨憨就会问了！这dp凭啥这样定义啊！：因为我们在某个位置上有没有火焰，单纯与上一位，本位和下一位有关。上一位可以在转移的体现，所以如此定义。
算法操作：
- 既然我们已经有了dp数组，这道题就简单很多了：我们分为四种情况进行递推，并写出转移方程。
- 本位为0的情况：自己不是火焰，两边也都不应该有火焰。
dp[i][0][0] = dp[i - 1][0][0] % MOD; //左式表示当前位和下一位均不为0，右式表示上一位和当前位均不为0（以下递推式均以此类推） //因为两侧都必须为0，所以只有这一种情况
- 本位为1的情况：自己不是火焰，左右又一边是火焰。
dp[i][0][0] = dp[i - 1][1][0] % MOD; //判定左边为火焰的情况：三个位置分别为1,0,0 dp[i][0][1] = dp[i - 1][0][0] % MOD; //判定右边为火焰的情况：三个位置分别为0,0,1
- 本位为2的情况：自己不是火焰，左右都是火焰。
dp[i][0][1] = dp[i - 1][1][0] % MOD; //因为两边都有火焰，所以只有一种情况：分别为1,0,1
- 本位为*的情况：自己是火焰，左右不知道（因为假如是数字就是表示这里有，不是数字也可以是？和*（连续雷嘛），所以最多只知道不能是0）。
dp[i][1][0] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD; //自己是火焰，假设后面不是，前面不能确定，所以两种情况可以加起来 dp[i][1][1] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD; //自己是火焰，假设后面也是，前面依旧不能确定，所以也是两种情况加起来
- 本位为?的情况：自己是啥不知道，左右是啥也不知道（所以这就包含了所有的可能性）。
dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][1][0]) % MOD; dp[i][0][1] = (dp[i - 1][0][0] + dp[i - 1][1][0]) % MOD; //假设本位不是是火焰，再讨论下一位 dp[i][1][0] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD; dp[i][1][1] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD; //假设本位是火焰，再讨论下一位
- 那么这些我们都知道了之后呢，我们还有一个很重要的东西：特殊条件。
- 我们的递推要考虑到前一位和后一位是什么，这就导致首尾比较特殊：首位没有上一位，尾位没有下一位。
- 所以我们将首尾都设置为0，防止影响到操作。
- 然后我们是从前往后递推的，所以我们就要初始化起始值：
dp[0][0][0] = dp[0][0][1] = 1;
我们是以首位的上一位为本位，所以在此位为0的时候，他的下一位无论是什么都是一种情况。
那么，打代码：
- 先输入我们的字符串，这里因为dp数组的首位特判，我们舍弃字符串的0位（方便编程）。
- 然后分类讨论进行递推（详情看上面）。
- 看代码吧~~~
AC代码
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
#define IOS ios::sync_with_stdio(false);
//代码预处理区
const int MOD = 1e9 + 7;
const int MAX = 1e6 + 7;
int dp[MAX][2][2];
//全局变量区
//函数预定义区
int main() {
IOS;
string s; cin >> s;
s = " " + s;
memset(dp, 0, sizeof dp);
dp[0][0][0] = dp[0][0][1] = 1;
int lens = s.length();
for (int i = 1; i < lens; i++)
if ('0' == s[i])
dp[i][0][0] = dp[i - 1][0][0] % MOD;
else if ('1' == s[i]) {
dp[i][0][0] = dp[i - 1][1][0] % MOD;
dp[i][0][1] = dp[i - 1][0][0] % MOD;
}
else if ('2' == s[i])
dp[i][0][1] = dp[i - 1][1][0] % MOD;
else if ('*' == s[i]) {
dp[i][1][0] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
dp[i][1][1] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
}
else if ('?' == s[i]) {
dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][1][0]) % MOD;
dp[i][0][1] = (dp[i - 1][0][0] + dp[i - 1][1][0]) % MOD;
dp[i][1][0] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
dp[i][1][1] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % MOD;
}
cout << (dp[lens - 1][0][0] + dp[lens - 1][1][0]) % MOD << endl;
return 0;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
