【滴滴笔试0907-2】动态规划-字符消除

10月26日，北京站源创会，聊聊高性能计算与大模型推理

题目描述

小明有一个长度为n，由前k个小写英文字母组成的字符串(保证n为偶数)。

小亮想在小明睡觉的时候把这个字符串用小明的零花钱消除干净。小亮每次可以选择该串的两个相邻的字符删除，删除后将串拼上，并花掉小明一定数量的零花钱。若某一次删除的相邻两个字符从左到右分别是a和b，则将花掉小明cost(a,b)块钱。小亮希望他花掉的零花钱尽可能多，帮帮小亮。

输入描述

第一行有两个整数n,k(1

接下来k行给出了一个k*k的由整数构成的矩阵。矩阵中第i行第j列的元素代表消除相邻的第i个字母和第j个字母所能花掉的钱数。

最后一行有一个长度为n的字符串，代表小明的字符串。

注意：

矩阵中的i,j从0开始计数，第i个字母表示相对于字母a来计数，如a为第0个字母，b为第1个字母。

输出描述

输出一个值，代表小亮最多能花掉小明多少零花钱。

题解

import java.util.*;

class Main {
    static Map cache = new HashMap<>();
    static int[][] arrCost;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int k = sc.nextInt();

        // 如果n小于2，则直接输出0并退出程序
        if (n < 2) {
            System.out.println(0);
            return;
        }

        // 创建一个k*k的二维数组arr
        int[][] arr = new int[k][k];

        // 填充二维数组arr
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                arr[i][j] = sc.nextInt();
            }
        }


        arrCost = arr;

        // 读取一个字符串
        String str = sc.next();

        // 将字符串转换为字符数组
        char[] strArr = str.toCharArray();

        // 调用getMaxConst方法计算最大成本
        int ans = getMaxConst(strArr, 0, n-1);

        // 输出计算结果
        System.out.println(ans);
    }


    private static int getMaxConst(char[] strArr, int begin, int end) {

        // 创建一个StringBuilder对象用于拼接字符串
        StringBuilder sb = new StringBuilder();

        // 将begin和end拼接到StringBuilder对象中
        String key = sb.append(begin).append("-").append(end).toString();

        // 如果缓存中存在该key，则直接返回缓存中的值
        if(cache.containsKey(key)) {
            return cache.get(key);
        }
        // 如果begin大于等于end，说明子字符串为空，返回0
        if(begin>=end) {
            return 0;
        }
        // 如果子字符串长度为2，则直接计算成本并返回
        if (end - begin == 1) {
            return getCost(strArr[begin], strArr[end]);
        }


        // 初始化最大成本为0
        int max = 0;
        // 遍历begin到end之间的所有可能分割点
        for (int i = begin+1; i <= end; i+=2) {
            // 计算当前分割点i对应的成本并更新最大成本
            max = Math.max(max, getCost(strArr[begin], strArr[i])+getMaxConst(strArr, begin+1, i-1)+getMaxConst(strArr, i+1, end));
        }
        // 将计算结果存入缓存
        cache.put(key, max);
        // 返回最大成本
        return max;
    }


    private static int getCost(char a, char b) {
        // 将字符a转换为其在字母表中的索引位置（从0开始）
        int ai = a - 'a';
        // 将字符b转换为其在字母表中的索引位置（从0开始）
        int bi = b - 'a';
        // 返回二维数组arrCost中对应索引位置的元素值
        return arrCost[ai][bi];
    }
}