拼多多算法笔试第4题期望题怎么做呀

第二题用滑动窗口只过了96

第三题怎么做，暴力直接栈爆炸，第四题是概率dp么,大家A了多少  啊

递归，做了15

第二题只过62.5，为什么😂

楼主第三题怎么做的啊🤣

我更惨 递推公式写错了 不知道哪错了     for (int i = 1; i < m; i++) {         res[i][1] = res[i - 1][1] * (1 - a) + res[i - 1][2] * (1 - a) * b + res[i - 1][3] * (1 - a) * b * b + res[i - 1][4] * (1 - a) * b * b * b;         res[i][2] = res[i - 1][1] * a + res[i - 1][2] * (1 - a) * (1-b) + res[i - 1][2] * a * b + res[i - 1][3] * a * b * b + res[i - 1][3] * (1- a) * b *(1-b) * 2 + res[i - 1][4] * b * b * (1-b)*3;         res[i][3] = res[i - 1][2] * a * (1 - b) + res[i - 1][3] * a * b * (1-b) * 2 + res[i - 1][3] * (1-a) * (1-b) * (1-b) + res[i - 1][4] * b * b * (1-b) * 3;         res[i][4] = res[i - 1][4] * (1 - b) * (1 - b) * (1 - b) + res[i][3] * a;         result += res[i][1];     }

第三题用映射 题目其实已经给了解法了 一个| 一个^ 2步必能映射所有答案 对于每一位，考虑本来是0还是1 经过所有运算之后会变成0还是1 假如0变成0 1 变成1 那就是 |0 ^0 0变成1 1变成0 就是|0 ^1 1变成0 0变成0 就是|1 ^1 剩下一种就是|1 ^1

动态规划就行了，ac

楼主，第四题的最后一个样例是多少哇？

我觉得第三题直接 先通过 & 映射到0然后再通过 I 映射到最后的结果，就可以了

用动态规划，python写的 dic = {} def factorial(n):     if n == 0:         return 1     if n == 1:         return 1     if n in dic:         return dic[n]     else:         dic[n] = n * factorial(n-1)         return dic[n]      def comb(a, b):     return int(factorial(a) / factorial(b) / factorial(a-b)) dp_table = [[0 for _ in range(n)] for _ in range(m)] dp_table[0][0] = 1 for j in range(1, n):     dp_table[0][j] = 0      for i in range(1, m):     for j in range(0, n):         if j == 0:             dp_table[i][j] = 1 + dp_table[i-1][j] * (1-a) + dp_table[i-1][j+1] * a         elif j == n - 1:             for k in range(n):                 dp_table[i][j] += comb(n-1, k) * b**k * (1-b)**(n-1-k)*dp_table[i-1][j-k]         else:             for k in range(j+1):                 dp_table[i][j] += comb(j, k) * b**k * (1-b)**(j-k)*(1-a)*dp_table[i-1][j-k]                 dp_table[i][j] += comb(j, k) * b**k * (1-b)**(j-k)*a*dp_table[i-1][j-k+1] print(dp_table[m-1][0])

这是正式批的笔试吗？