谷歌店面面经

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

其实有点像背包 ...

确实要开个二维数组用DP，这个做法是对的

感觉象个01背包问题， 写了一下， 不知道对不对， 请指正：

1. public static double divideMoney(List<Integer> list){
   
2.             if(list==null || list.size()==0) return 0.0;
   
3. 
   
4.             int sum=0;
   
5.             for(int n : list) sum+=n;
   
6.             
   
7.             return helperBack(list, sum/2)*1.0/Math.pow(2, list.size());
   
8.         }
   
9.         public static int helperBack(List<Integer> list, int target){
   
10.                 int[] dp=new int[target+1];
    
11.                 dp[0]=1;
    
12.                
    
13.                 for(int i=0; i<list.size(); i++){
    
14.                         for(int j=target; j>=1; j--){
    
15.                                 if(j>=list.get(i)) dp[j]+=dp[j-list.get(i)];
    
16.                         }
    
17.                 }
    
18.                 System.out.println("Tie: "+dp[target]);
    
19.                 return dp[target];
    
20.         }

复制代码

domofeng 发表于 2016-9-14 04:32
感觉象个01背包问题， 写了一下， 不知道对不对， 请指正：

SO上有一样的回答，感觉应该对的，这道题应该是pseudo polynomial的

补充内容 (2016-9-18 10:38):
不对，貌似有点小bug，j的初始化不是直接等于target

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

大神，
第一问，算下A, B分别拿走多少钱
是怎么理解的。。。。 他们在抛硬币决定谁拿，怎么知道A，B各拿多少呢。
这是个什么问题

和Combination Sum IV差不多,只是这里要求每个硬币不能重复,我们可以用个visited来避免重复.
dp+back tracking

我想问一下，当我们算出来一共有 k 个不同tie的情况．　那么概率就是　k / 2^n ? 这里 n 是指数组的长度．

AB钱相同的概率怎么算啊