字节笔试第4题 有大佬写出来了吗
就是小明小红掷骰子那题。 不知道回溯剪枝能不能过,复杂度很高但能剪一部分，最后时间不够了没写完。
#字节跳动##校招##笔试##字节23秋招笔试太难了吧#
有没有大佬有数学方法或者其他方法的，求个思路
前3题做完了还剩50分钟，怎么都想不出来，急了
-----补充-------
刚刚又做了一下，贴个代码，样例过了，应该没啥问题吧。
哎，剑指那题我还做过，忘了，有点亏。
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] arrA = new int[n];
int[] arrB = new int[m];
for (int i = 0; i < n; ++i) {
arrA[i] = sc.nextInt();
}
for (int i = 0; i < m; ++i) {
arrB[i] = sc.nextInt();
}
long[][] pA = dp(arrA);
long[][] pB = dp(arrB);
for (int i = 1; i < 161; ++i) {
pB[m][i] += pB[m][i - 1];
}
long sumA = 0;
for (int i = 0; i < 161; ++i) {
sumA += pA[n][i];
}
double p = 0;
for (int i = 1; i < 161; ++i) {
p += ((double) pA[n][i] / sumA) * ((double) pB[m][i - 1] / pB[m][160]);
}
System.out.println(p);
}
private static long[][] dp(int[] arr) {
long[][] p = new long[arr.length + 1][161];
p[0][0] = 1;
for (int i = 1; i <= arr.length; ++i) {
for (int j = i; j <= 8 * i; ++j) {
for (int k = 1; k <= arr[i - 1]; ++k) {
if (j - k >= 0)
p[i][j] += p[i - 1][j - k];
}
}
}
return p;
}
}
