滴滴笔试零花钱
比如[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]; } }