这是道比较经典的线性DP问题,当前的决策与上次决策有关,是 打家劫舍 的变形题
定义 dp[i][j] 表示,当前考虑到第 i 个数,且上一次选的字母是 j 的所有合法方案数。
状态转移为: dp[i][j]=∑k=jdp[i−1][k]。
即前 i 天选择字符 j 对应商家的方案数,等于前 i−1 天选择除 j 以外任意字符的方案数之和。
小美经常去美团上点外卖,她给自己规划了每天会在哪些商家中选择一家来点。
由于怕吃腻,小美决定不会连续两天点同一个商家。现在请你判断小美有多少种不同的选择方案?
第一行输入一个正整数n,代表小美点外卖的天数。
接下来的n行,每行输入一个长度不超过20的字符串,代表小美每天的选项。相同的字符代表同一个商家。
1≤n≤105
保证每个字符串内的字符都不同。
输出一个整数,代表小美点外卖的方案数。由于答案过大,请对109+7取模
输入
2
ab
bcd
输出
5
说明
方案 1:第一天点商家 a,第二天点商家 b。
方案 2:第一天点商家 a,第二天点商家 c。
方案 3:第一天点商家 a,第二天点商家 d。
方案 4:第一天点商家 b,第二天点商家 c。
方案 5:第一天点商家 b,第二天点商家 d。