Google MTV 4/14 面经

hotIce 发表于 2015-4-21 11:57
三维dp O(num0 * num1 * sizeof(array))
dfs我感觉是exponential

dp 的复杂度还有再乘以最长字符串长度~

houqingniao 发表于 2015-4-21 23:09
dp 的复杂度还有再乘以最长字符串长度~

先预处理下字符串数组就行了 每个字符串数下有几个０和１除非有很长很长的字符串 否则不影响时间复杂度

hotIce 发表于 2015-4-22 01:29
先预处理下字符串数组就行了 每个字符串数下有几个０和１除非有很长很长的字符串 否则不影响时间复杂度

可以麻烦写一下转移方程么，想了好久。多谢啦

xuepanchen 发表于 2015-4-21 09:32
你可以看一下板凳同学写的解法，很棒。
我当时就是最直白的用了四个变量存了白白，白黑，黑白，黑黑这四 ...

这个题做成这样，就可以用矩阵乘法来做到logN了。

Linzertorte 发表于 2015-4-23 12:40
这个题做成这样，就可以用矩阵乘法来做到logN了。

能说一下怎么用矩阵乘法嘛嘻嘻

hotIce 发表于 2015-4-22 01:29
先预处理下字符串数组就行了 每个字符串数下有几个０和１除非有很长很长的字符串 否则不影响时间复杂度

同求预处理完之后的转移方程

xuepanchen 发表于 2015-4-25 02:23
能说一下怎么用矩阵乘法嘛嘻嘻

http://community.topcoder.com/st ... =11512&rd=14546

celtspirit 发表于 2015-4-23 11:51
可以麻烦写一下转移方程么，想了好久。多谢啦

dp[m][n][i] represents the maximum number of string to choose for m zeros and n ones in [0...i - 1] subarray
assume ith element has x zeros and y ones
dp[m][n][i] = (m - x >0 && n - y > 0) ? max(dp[m][n][i - 1], dp[m - x][n - y][i - 1] + 1) : dp[m][n][i - 1];
dp[m][n][0] = 0;