谷歌店面面经

phantom 发表于 2016-9-9 02:12
https://en.wikipedia.org/wiki/Partition_problem#The_pseudo-polynomial_algorithm

其实有点像背包 ...

这个跟我上面写的有点像，都是要sum长度的数组。求问这种解法最后的概率是dp[sum/2][n]/(2^n)？

Josh 发表于 2016-9-9 02:32
这个跟我上面写的有点像，都是要sum长度的数组。求问这种解法最后的概率是dp[sum/2][n]/(2^n)？

嗯。。是的啊。。

确实很像啊。。都需要sum长度的数组。。

能不能用类似coin change的dp解法来解？
sort 数组以后
dp[i] 表示 i块钱可以有dp[i]种组合

william_gong 发表于 2016-9-9 02:37
能不能用类似coin change的dp解法来解？
sort 数组以后
dp 表示 i块钱可以有dp种组合

不一样，coin change里面硬币可以重复利用，这里硬币用完就没了。至少要二维数组吧，一个记录钱数，一个记录硬币数

Josh 发表于 2016-9-9 02:42
不一样，coin change里面硬币可以重复利用，这里硬币用完就没了。至少要二维数组吧，一个记录钱数，一个 ...

嗯对，确实是我欠考虑了

Josh 发表于 2016-9-9 02:42
不一样，coin change里面硬币可以重复利用，这里硬币用完就没了。至少要二维数组吧，一个记录钱数，一个 ...

那用 Combination Sum IV 的思路呢？

william_gong 发表于 2016-9-9 02:47
那用 Combination Sum IV 的思路呢？

第一问是combination sum吧，第二问dp肯定更快，combination sum是O(2^n)

Josh 发表于 2016-9-9 02:57
第一问是combination sum吧，第二问dp肯定更快，combination sum是O(2^n)

不是吧， Combination Sum IV是dp解的， 复杂度是n方， n为数组长度

william_gong 发表于 2016-9-9 03:01
不是吧， Combination Sum IV是dp解的， 复杂度是n方， n为数组长度

sorry理解错了，原来你指的是CombinationIV，那个题也是可以重复的，跟coin change是一样的

phantom 发表于 2016-9-9 02:12
https://en.wikipedia.org/wiki/Partition_problem#The_pseudo-polynomial_algorithm

其实有点像背包 ...

赞！谢谢指点哇