滴滴笔试零花钱

比如[a, b, c, d, e, f]这个数组，a可以和b、d、f消除，枚举遍历可消除的元素，分治递归计算出最大花费的值。

对于同一个区间花费的零花钱的值的最大值是相同的，所以记得加上记忆化搜索，否则正确率是27%

import java.util.*;

public class Main {
    static Map<String, Integer> 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();
        if (n < 2) {
            System.out.println(0);
            return;
        }
        int[][] arr = new int[k][k];
        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();
        int ans = getMaxConst(strArr, 0, n-1);
        System.out.println(ans);
    }

    private static int getMaxConst(char[] strArr, int begin, int end) {
        StringBuilder sb = new StringBuilder();
        String key = sb.append(begin).append("-").append(end).toString();
        if(cache.containsKey(key)) {
            return cache.get(key);
        }
        if(begin>=end) return 0;
        if (end - begin == 1) {
            return getCost(strArr[begin], strArr[end]);
        }
        int max = 0;
        for (int i = begin+1; i <= end; i+=2) {
            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) {
        int ai = a - 'a';
        int bi = b - 'a';
        return arrCost[ai][bi];
    }

}