题解

这是道比较经典的线性DP问题，当前的决策与上次决策有关，是 打家劫舍 的变形题

定义 $dp[i][j]$ 表示，当前考虑到第 $i$ 个数，且上一次选的字母是 $j$ 的所有合法方案数。

状态转移为： $dp[i][j] = \sum_{k \neq j} dp[i-1][k]$。

即前 $i$ 天选择字符 $j$ 对应商家的方案数,等于前 $i-1$ 天选择除 $j$ 以外任意字符的方案数之和。

本题采用记忆化搜索的方式来实现

递归入口：$dfs(0, 26)$ , 其中 $26$ 表示上一家未选

递归边界 $u == n$ ：表示找到一组合法的方案数，返回 $1$

AC代码

c++

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
int main (){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n; cin >> n;
    vector<string> v(n);
    for(int i = 0; i < n; i ++)
        cin >> v[i];
    vector<vector<int>> dp(n + 1, vector<int>(27, -1));
    auto dfs = [&](auto dfs, int u, int pre) -> int
    {
        if(u == n)
            return 1;
        if(dp[u][pre] != -1)
            return dp[u][pre];
        int res = 0;
        for(char ch : v[u])
        {
            if(ch - 'a' != pre)
                res += dfs(dfs, u + 1, ch - 'a'), res %= mod;
        }
        dp[u][pre] = res;
        return res;
    };
    cout << dfs(dfs, 0, 26);
    return 0;
}

python

n=int(input())
pre_s=input().strip()
pre_dp=[1]*len(pre_s)
res=0
for i in range(1,n):
    s=input().strip()
    dp=[0]*len(s)
    for j in range(len(s)):
        index=pre_s.find(s[j])
        if index>=0:
            dp[j]=sum(pre_dp)-pre_dp[index]
        else:
            dp[j]=sum(pre_dp)
    pre_dp=dp[:]
    pre_s=s
print(sum(dp)%(10**9+7))

java

import java.util.*;
// 注意类名必须为Main
class Main {
    static int n;
    static long res = 0;
    static long mod = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        String s1 = sc.next();
        HashMap<Character,Long> map1 = new HashMap<>();
        for(int i=0;i<s1.length();i++){
            map1.put(s1.charAt(i),1L);
        }
        res = map1.size();
        for(int i=1;i<n;i++){
            String s2 = sc.next();
            HashMap<Character,Long> map2 = new HashMap<>();
            long t = 0;
            for(int ii=0;ii<s2.length();ii++){
                char c = s2.charAt(ii);
                if(map1.get(c) == null){
                    map2.put(c,res);
                    t += res;
                }else{
                    if(res-map1.get(c)<0){
                        map2.put(c,res-map1.get(c)+mod);
                        t += res-map1.get(c)+mod;
                    }else{
                        map2.put(c,res-map1.get(c));
                        t += res-map1.get(c);
                    }
                }
                t %= mod;
            }
            map1 = map2;
            res = t;
            // for(char c:map1.keySet()){
            //     res += map1.get(c);
            //     res %= mod;
            // }
            // res %= mod;
        }
        
        System.out.println(res);
    }
}

题目描述

小美经常去美团上点外卖，她给自己规划了每天会在哪些商家中选择一家来点。

由于怕吃腻，小美决定不会连续两天点同一个商家。现在请你判断小美有多少种不同的选择方案？

输入描述

第一行输入一个正整数$n$，代表小美点外卖的天数。

接下来的$n$行，每行输入一个长度不超过20的字符串，代表小美每天的选项。相同的字符代表同一个商家。

$1\le n\le 10^5$

保证每个字符串内的字符都不同。

输出描述

输出一个整数，代表小美点外卖的方案数。由于答案过大，请对$10^9+7$取模

样例

输入

2
ab
bcd

输出

5

说明

方案 1：第一天点商家 a，第二天点商家 b。
方案 2：第一天点商家 a，第二天点商家 c。
方案 3：第一天点商家 a，第二天点商家 d。
方案 4：第一天点商家 b，第二天点商家 c。
方案 5：第一天点商家 b，第二天点商家 d。