动态规划法解数字加符号的运算结果

元始天尊

今天看到有同学华为面试，而我痛苦去不了，在外实习赶不上啊。
看到很多论坛讨论这样一道题：
1,2,3,....9 n个数，每个数字前可以加'+' '-' 或空，要求输出所有满足计算结果为某数的所有表达式

我刚看到这个问题就觉得可以用动态规划做，经过一阵研究得出下面递推式：
F(n,m)=∩F(k-1,m±Interger(a[k,n]))   遍历k∈[0,n-1]  如果不存在k则在数组[0-n]范围内无法找到结果为m的表达式
反之则在n=0时输出。
欢迎大家一起测试。

代码如下：

1. 
   
2. #include <iostream>
   
3. using namespace std;
   
4. 
   
5. #define arr(x,y) arr[(x)*size2+(y)]
   
6. 
   
7. const int num=9;
   
8. int arr[num]={1,2,3,4,5,6,7,8,9};//第一个数之前也可以有符号
   
9. char sig[num];
   
10. 
    
11. int getmax(int i,int j)
    
12. {
    
13.         int result=0;
    
14.         for(int k=i;k<=j;k++)
    
15.                 result=result*10+arr[k];
    
16.         return result;
    
17. }
    
18. 
    
19. bool func(int n,int m)
    
20. {//F[n,m]用来求arr[0-n]内运算产生结果m的所有解
    
21.         int j;
    
22.         //结果
    
23.         if(m == 0 || n == 0)
    
24.         {
    
25.                 if(m == 0)
    
26.                 {
    
27.                         for(int k=0;k<num;k++)
    
28.                         {
    
29.                                 cout<<sig[k]<<arr[k];
    
30.                         }
    
31.                         cout<<endl;
    
32.                 }
    
33.                 if(n == 0)
    
34.                 {
    
35.                         if(arr[n] == m)
    
36.                         {
    
37.                                 sig[0]='+';
    
38.                                 for(int k=0;k<num;k++)
    
39.                                 {
    
40.                                         cout<<sig[k]<<arr[k];
    
41.                                 }
    
42.                                 cout<<endl;
    
43.                                 return true;
    
44.                         }
    
45.                         else if(arr[n] == -m)
    
46.                         {
    
47.                                 sig[0]='-';
    
48.                                 for(int k=0;k<num;k++)
    
49.                                 {
    
50.                                         cout<<sig[k]<<arr[k];
    
51.                                 }
    
52.                                 cout<<endl;
    
53.                                 return true;
    
54.                         }
    
55.                         else
    
56.                                 return false;
    
57.                 }
    
58.                 return true;
    
59.         }
    
60. 
    
61.         //限界
    
62.         if(n < 0)
    
63.                 return false;
    
64.         int curmax=getmax(0,n);
    
65.         if(m > curmax || m < -curmax)
    
66.                 return false;
    
67.        
    
68. 
    
69.         //动态规划F(n,m)=∩F(k-1,m±Interger(a[k,n]))   遍历k∈[0,n-1]
    
70.         bool ret=false;
    
71.         for(int k=0;k<=n;k++)
    
72.         {
    
73.                 int max=getmax(k,n);
    
74.                 sig[k]='+';
    
75.                 for(j=k+1;j<=n;j++)
    
76.                         sig[j]='\0';
    
77.                 if(func(k-1,m-max))
    
78.                 {
    
79.                         ret=true;
    
80.                 }
    
81.                        
    
82.                 sig[k]='-';
    
83.                 for(j=k+1;j<=n;j++)
    
84.                         sig[j]='\0';
    
85.                 if(func(k-1,m+max))
    
86.                 {
    
87. 
    
88.                         ret=true;
    
89.                 }
    
90.         }
    
91. 
    
92.         return ret;
    
93. }
    
94. 
    
95. void main()
    
96. {
    
97.         int i,j;
    
98.         int object=123;
    
99. 
    
100. 
     
101.         func(num-1,object);
     
102. }
     

复制代码

对于n:1-9  m:123，可以得到如下结果：
-1-2 3-4-5+6 7+8 9
-1-2 3+4 5+6+7+8 9
-1+2 3+4-5+6+7+8 9
+1+2 3+4+5-6+7+8 9
+1-2+3+4 5-6-7+8 9
-1-2 3+4+5 6+7 8+9
-1 2-3+4 5+6+7 8+9
-1+2+3 4-5+6+7 8+9
-1-2-3+4 5-6+7 8+9
+1+2+3 4+5-6+7 8+9
-1-2-3+4 5+6 7+8+9
-1-2+3 4+5+6 7+8+9
-1-2-3+4+5 6+7 8-9
+1-2+3-4+5 6+7 8-9
-1-2+3+4 5+6+7 8-9
+1 2+3+4 5-6+7 8-9

m=45时（我以为只有连加呢，，结果结果出了一大堆）
+1-2 3+4 5-6 7+8 9
-1+2 3-4+5-6 7+8 9
+1+2 3+4-5-6 7+8 9
-1-2+3+4-5 6+7+8 9
+1 2-3-4-5 6+7+8 9
-1-2-3-4 5-6+7+8 9
+1 2+3+4-5 6-7+8 9
-1+2 3-4-5 6-7+8 9
+1-2+3-4 5+6-7+8 9
-1-2-3 4+5-6-7+8 9
+1-2 3-4-5-6-7+8 9
-1+2 3+4 5+6 7-8 9
-1-2-3-4 5+6+7 8+9
+1 2-3-4 5-6+7 8+9
+1+2-3 4-5-6+7 8+9
+1+2+3-4 5+6 7+8+9
-1-2-3 4-5+6 7+8+9
+1-2-3 4+5 6+7+8+9
+1+2+3+4+5+6+7+8+9
+1+2 3-4-5+6+7+8+9
-1 2+3 4+5-6+7+8+9
-1-2+3 4-5-6+7+8+9
-1-2+3 4-5+6-7+8+9
+1-2-3+4 5-6-7+8+9
-1+2+3 4+5-6-7+8+9
+1 2+3 4-5-6-7+8+9
-1+2 3-4 5+6 7-8+9
-1-2 3-4+5+6 7-8+9
+1-2 3+4-5+6 7-8+9
-1-2 3+4+5 6+7-8+9
-1 2-3-4+5 6+7-8+9
-1+2 3+4+5+6+7-8+9
-1+2+3 4-5+6+7-8+9
-1+2-3+4 5-6+7-8+9
-1 2+3+4+5 6-7-8+9
-1+2-3-4+5 6-7-8+9
-1-2-3+4 5+6-7-8+9
-1-2+3 4-5 6+7 8-9
+1 2+3-4 5+6+7 8-9
+1-2-3 4+5+6+7 8-9
-1 2+3-4-5-6+7 8-9
+1+2 3-4 5+6 7+8-9
+1-2 3-4+5+6 7+8-9
+1+2 3+4+5+6+7+8-9
-1-2-3+4 5-6+7+8-9
-1-2+3-4+5 6-7+8-9
+1-2+3+4 5+6-7+8-9
-1-2-3-4+5+6 7-8-9
-1-2-3-4-5+6 7-8-9
-1-2-3+4+5 6+7-8-9
-1-2+3-4+5 6+7-8-9
-1+2+3+4 5+6+7-8-9
+1 2-3+4+5 6-7-8-9