[动态规划-4] 合并数

比如num = [5, 5, 10, 2, 3]，给定的合并值为 15 :

有4种 ： ｛5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3｝

 

分析：

 

这实际上是网易有道笔试题之一，我觉得我笔试通过主要就是依靠这个题目，因为其他的做的比较一般。

 

这道题使用动态规划思想，大家看如下的状态转移方程：

 

dp[n][m]=dp[n-1][m]+dp[n-1][m-num[n-1]]；//这里的num[n-1]是第n个数字

 

dp[n][m]表示前n个元素组成和为m的情况数。初始化dp[0][0]=1，其他为0。写出状态转移方程，大家也就明白了，为何要求全是正数了吧，直白一些，数组的索引，怎么可能为负呢？在计算的过程中，将和的情况保存下来，用空间换时间，整个算法的时间复杂度为O(n*m)，不再是指数级。

 

代码：

 

 

 

#include<iostream>  
#include<vector>  
  
using namespace std;  
  
int merge(int num[], int n, int sum)  
{  
    if(n < 1 || !num || sum<0)  
       return 0;  
    vector<int> dp[n+1];  
    for(int i =0;i<= n;i++)  
        dp[i].resize(sum+1);  
      
    for(int i = 1;i<=sum;i++)  
        dp[0][i] = 0;//用前0个数表示任何非0的数字都有0种方法   
    for(int i = 0;i<=n;i++)  
        dp[i][0] = 1;//用数组中的任何数表示0都只有一种方法，那就是什么都不取   
    for(int i = 1;i<=n;i++)  
        for(int j = 1;j<=sum;j++)  
        {  
          int tmp1 = dp[i-1][j];  
          int tmp2 = 0;  
          if(j - num[i-1]>= 0)   
              tmp2 = dp[i-1][j-num[i-1]];  
          dp[i][j] = tmp1 + tmp2;               
        }  
      
    //打印出数组来看看更直观，可以省略   
    for(int i = 0;i<=n;i++)  
    {  
      for(int j = 0;j<=sum;j++)  
        printf("%d ",dp[i][j]);  
      printf("\n");  
    }  
    return dp[n][sum];  
}  
  
  
  
int main()  
{  
 int num[] = {5,5,10,2,3};  
  
 printf("%d\n",merge(num,5,15));  
 system("pause");  
 return 0;  
}  

 

 

补充：软件开发 , C++ ,