发一个yelp的skype电面面经，已跪

用 dfs 解？
class Solution{
        public boolean dartGame(int[] score, int target){
                return helper(new int[score.length], score, target);
        }

        private boolean helpeR(int[] mark, int[] score, int target){
                for(int i=0; i< mark.length; i++){
                        if(!mark[i] || target < score[i]){
                                continue;
                        }
                        if(target == score[i]){
                                return true;
                        }
                        mark[i] = true;
                        if(helper(mark, score, target - score[i])){
                                return true;
                        }else{
                                mark[i] = false;
                        }
                }
                return false;
        }
}

请问LZ你面的是哪一个组？

这不是类似dp的背包问题吗？

请问楼主第一轮HR电话有问一些概念问题么？什么database join, ssl缩写啥的？

楼主海投拿到面试，一定背景很强666

AndyLiu0429 发表于 2015-7-20 17:18
dp可以解决吧。。不排序的话就是没法去重了。

感觉不需要去重吧,最后求的是能否组成给定分数,如果可以组成的话,dp[k]最后一定是true吧

这个可以用经典的coin change方法,大概就是背包问题,楼主可以看下leetcode的coin change题

1. class Solution(object):
   
2.     def dartGame(self, scores, target):
   
3.         """
   
4.         :type scores: List[int]
   
5.         :rtype: Bool
   
6.         """
   
7.         scores.sort()
   
8.         return self.dfs(scores, target)
   
9. 
   
10. 
    
11.     def dfs(self, scores, target):
    
12.         if target==0:
    
13.             return True
    
14. 
    
15.         if target<0 or not scores:
    
16.             return False
    
17. 
    
18.         for i in range(len(scores)):
    
19.             if scores[i]<=target:
    
20.                 if self.dfs(scores[i+1:], target-scores[i]):
    
21.                     return True
    
22.         return False
    
23. 
    
24. 
    
25. scores = [3,5,3,3,5]
    
26. target = 7
    
27. so = Solution()
    
28. a = so.dartGame(scores, target)
    
29. print a

复制代码

there you go

每次从n里面减去一个数，然后从list里面pop掉减去的这个数，重复上述过程直到n变成0。如果任何情况下都无法得到0, 返回False。时间复杂度exponential

1. def valid_score(lst, n):
   
2.     if n == 0:
   
3.         return True
   
4. 
   
5.     for i, num in enumerate(lst):
   
6.         if valid_score(lst[:i] + lst[i+1:], n - num):
   
7.             return True
   
8. 
   
9.     return False

复制代码