[互联网面试笔试汇总C/C++-3] 网易有道-2

1、求正数数组内和为指定数字的合并总数
比如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]]
 
dp[n][m]表示前n个元素组成和为m的情况数。初始化dp[0][0]=1，其他为0。写出状态转移方程，大家也就明白了，为何要求全是正数了吧，直白一些，数组的索引，怎么可能为负呢？在计算的过程中，将和的情况保存下来，用空间换时间，整个算法的时间复杂度为O(n*m)，不再是指数级。
 
具体代码将会后续贴出，大家先根据这个思路自己分析一下~也欢迎大家提出自己的思路哈~

补充：软件开发 , C语言 ,

上一个：[互联网面试笔试汇总C/C++-4] 进程和线程的区别
下一个：[互联网面试笔试汇总C/C++-2] 网易有道-1