密室闯关

#动态规划
def dp(n,s):
    if s==0:return 1
    if n==1:return 1
    obj = [[0]*(s+1) for _ in range(n+1)]
    for j in range(min(26,s+1)):
        obj[1][j] = 1
    for i in range(2,n+1):
        obj[i][0] = 1
        for j in range(max(s-25*(n-i),0),s+1):
            obj[i][j] = (sum(obj[i-1][j-min(25,j):j+1])) % mo
    return obj[n][s]

"""
#递归
def dp(n,s):
    if s==0:return 1
    elif n==1:
        if s<min(26,s+1):return 1
        else:return 0
    else:
        a = 0
        for k in range(min(26,s+1)):
            a = (a+dp(n-1,s-k)) % mo
        return a
"""

while 1:
    try:
        n = int(input())
        aim = list(input())
        s = 0
        mo = 998244353
        for i in range(n):
            s += (ord(aim[i])-65)
        print(dp(n,s))
    except: break

如果该齿轮上的字母是Z，该齿轮按下按钮后也不能移动。

这句话我认为应该去掉

思路：

先转化，抽象出数学语言：
给你一个长度的数组,你每次可以进行如下2个操作,但得保证操作后的数组
(1)
(2)
你可以进行任意次合法操作，问你状态数目

emm这其实演示的是由某一个解得到【total:=\sum{char-'A'+1}的n个和数且和数在[1,26]的Composition的全部解】的过程。

要求的就是total:=\sum{char-'A'+1}分解为n个和数且和数在[1,26]范围内的Composition方案数目

下面的代码利用了公式
n分解为k个和数且和数在[1,r]范围内的Composition方案数目

#include
using namespace std;
typedef long long ll;
#define mod 998244353
string s;
ll n;
ll b[6010][6010];
void GetBinomial(){
    for(int i=0;i<=6005;i++) b[i][0]=1;
    for(int  i=1;i<=6005;i++){
        for(int  j=1;j<=i;j++){
            b[i][j]=(b[i-1][j]+b[i-1][j-1])%mod;
        }
    }
} 
ll Comp_n_summands_EachRange_1R(ll n,ll k, ll r){//n的k个和数且和数在[1,r]的Composition的方案数目 
    ll sum=0;
    if(r<=0) return 0;
    if(k<=0) return 0;
    for(ll j=0;j<=k&&j<=(n-k)/r ;j++){
        if(j&1){
            sum=(sum+mod-b[k][j]*b[n-r*j-1][k-1]%mod)%mod;
        }
        else {
            sum=(sum+b[k][j]*b[n-r*j-1][k-1]%mod)%mod;
        }
    }
    return sum;
}
int main(){
    GetBinomial();
    while(cin>>n>>s){
        ll total=0;
        for(ll i=0;i<n;i++)  total+=(s[i]-'A'+1);
        //cout<<"total"<<total<<endl; 
        cout<<Comp_n_summands_EachRange_1R(total,n,26)<<endl;
    }
    return 0;
}

根据热评第一大佬的思路写了一个java版本。
这题和第二题是相同类型，都是n个数构成目标和sum的方案数，只不过每个题都有一些不同的变化。我不知道美团真实笔试是否是这样类型的，前面做了一套也是，2和4是相同类型的图的遍历问题。
过几天会投简历，去试一下真实的笔试现场

import java.util.*;
import java.lang.*;

public class Main{
    static long mod = 998244353;
    // 题目中并没有给n的范围，这个是试出来的，99也可以
    static int maxn = 100;
    static int maxSum = maxn * 26;
    static long[][] dp = new long[maxn+1][maxSum+1];
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        initDP();
        while(sc.hasNextLine()){
            int n = sc.nextInt();
            sc.nextLine();
            String s = sc.nextLine();
            int sum = 0;
            for(int i=0;i<n;++i){
                sum += (s.charAt(i)-'A');
            }
            System.out.println(dp[n][sum]);
        }
    }

    // 求n个0-25的数，组成和为sum的方案数
    // dp[n][sum]
    public static void initDP(){
        // n个数和为0，方案只有1种
        for(int i=0;i<=maxn;++i){
            dp[i][0] = 1;
        }
        // i个数
        for(int i=1;i<=maxn;++i){
            // 目标和为j
            for(int j=1;j<=maxSum;++j){
                // 填入的当前数,0-25,且<=目标和j
                for(int k=0;k<26 && k<=j;++k){
                    dp[i][j] += dp[i-1][j-k];
                    dp[i][j] %= mod;
                }
            }
        }
    }
}

将齿轮上的字母映射为权重： A = 0，B = 1，......，Z = 25。通过齿轮的转动，不同齿轮之间的权重可以相互转移，但是所有齿轮的权重和会保持不变，并且每个齿轮的权重只能在 [0, 25]

假设所有齿轮的权重和等于 sum，共有 n 个齿轮，题目就等价于：将 sum 分成有序的 n 份，且每一份都必须在区间 [0, 25] 之间，求总共有多少种方案？

这里采用动态规划分析：

• 第一步，设 dp[i][j] 表示，将权重 j 分成有序的 i+1 份，总共有几种方案

• 第二步，第 i 个可以是 0~25，所以 dp[i-1][j] 等于：

• 第三步，初始化

  • dp[0][j] = (j ≥ 0 && j ≤ 25) ? 1 : 0

  • dp[i][0] = 1

• 第四步，遍历方向，i 从小到大遍历，j 从小到大

• 第五步，自己手动演示一下案例，加深理解~

优化：其实不管字符是怎么样的，只要 sum 相等、n 相等，结果一定是相等的。所以我们可以一次性算完所有的 dp，后续输入任何案例从 dp 数组中获取即可，而不是每输入一个案例就 dp 一次。这里可以尝试案例，n 最大是 100 ~

import java.util.*;
import java.io.*;

public class Main {
    private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int maxN = 100;
    private static int maxSum = 2500;
    // dp[i][j] 表示，将权重 j 分成有序的 i+1 份，总共有几种方案
    private static int[][] dp = new int[maxN][maxSum + 1];

    // 初始化 dp
    private static void initDp() {
        // 初始化
        for (int j = 0; j <= maxSum; ++j) {
            dp[0][j] = (j >= 0 && j <= 25) ? 1 : 0;
        }
        for (int i = 0; i < maxN; ++i) {
            dp[i][0] = 1;
        }
        // 遍历
        for (int i = 1; i < maxN; ++i) {
            for (int j = 1; j <= maxSum; ++j) {
                for (int k = 0; k <= 25 && k <= j; ++k) {
                    dp[i][j] += dp[i-1][j-k];
                    dp[i][j] %= 998244353;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        initDp();
        String line = null;
        while (true) {
            line = reader.readLine();
            if (line == null) {
                break;
            }
            // 获取 n 和 sum
            int n = Integer.parseInt(line);
            line = reader.readLine();
            int sum = 0;
            for (int i = 0; i < n; ++i) {
                sum += (line.charAt(i) - 'A');
            }
            // 从 dp 中获取结果
            writer.write("" + dp[n-1][sum]);
            writer.newLine();
        }
        writer.flush();
    }
}