问题描述

小红在研究古代遗留下来的魔法阵时发现了一系列神秘的符号。这些符号代表着不同的魔法能量：未知能量用“？”表示，已爆发的能量用“*”标记。每一个没有能量爆发的符号位置上有一个数字（0 到 2），这个数字表示该位置左右两侧已爆发能量的总数。现在小红想要确定所有可能的已爆发能量分布情况的数量。

题解

本题是 codeforces 难度分为 1900分的原题 链接

由于本题是有后效性的动态规划，直接递推比较难写，这边采用记忆化搜索的方法来写

定义 $dfs(i,j)$ 表示考虑 $s[0] ... s[i]$，$j=0/1/2$ ，分别为：$s[i]$ 不能是雷/ $s[i]$ 一定是雷/ $s[i+1]$ 是雷

返回在这种情况下的方案数。