华为面试题，求答案？

koolcoy

动态规划 + hash滤重，复杂度2^N， 目前没更好的算法

koolcoy

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int main() {
   
5.         int input[8] = {1,2,3,4,5,6,7,8};
   
6.         int sum[256];
   
7. 
   
8.         sum[0] = 0;
   
9.         sum[1] = input[0];
   
10. 
    
11.         int idx = 2;
    
12.         for (int i = 1; i < 8; ++i, idx *= 2) {
    
13.                 for (int j = 0; j < idx; ++j) {
    
14.                         sum[idx + j] = input[i] + sum[j];
    
15.                 }
    
16.         }
    
17.         for (int i = 0; i < 256; ++i) {
    
18.                 printf("%d ", sum[i]);
    
19.         }
    
20.         return 0;
    
21. }
    

复制代码

DP差不多就这个意思

koolcoy

回复 12# udb6688

基本就这么个意思，调试一下就能找到哪里不对了
   

koolcoy

我那个代码应该没有错，这么改一下就很清晰了：

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int main() {
   
5.         unsigned long input[8] = {1, 10, 100, 1000, 10000, 100000, 1000000,
   
6.                 10000000};
   
7.         unsigned long sum[256];
   
8. 
   
9.         sum[0] = 0;
   
10.         sum[1] = input[0];
    
11. 
    
12.         int idx = 2;
    
13.         for (int i = 1; i < 8; ++i, idx *= 2) {
    
14.                 for (int j = 0; j < idx; ++j) {
    
15.                         sum[idx + j] = input[i] + sum[j];
    
16.                 }
    
17.         }
    
18.         for (int i = 0; i < 256; ++i) {
    
19.                 printf("%08lu\n", sum[i]);
    
20.         }
    
21.         return 0;
    
22. }
    

复制代码

koolcoy

回复 16# udb6688

因为sum[0]和sum[1]已经赋值了，所以就从sum[2]开始算起