请教一个求数组部分和的是否等于某数的算法

emacsnw

原帖由 ArXoR 于 2006-2-14 04:53 发表
用hash表,
扫描一遍数组
到Ai时,计算到此位置时的部分和Si,
在hash表里查询Si-M
然后把(Si,i)插入hash表
扫描完找到最小k就结束了

hash表里对于Si相同的节点,保存更新的位置

O(n)的复杂度和空间复杂度

什么叫做到Ai时的部分和Si？怎么更新Si？不会是从头加到Ai吧？

emacsnw

原帖由 fsilence 于 2006-2-14 03:27 发表
假如有一个数组A，数组元素个数为SIZEA，现在给你一个整数M，求一个最小整数k，使得k个数组元素之和等于M，注意这里要保证k最小，如果不存在这样的k返回-1。

可以用动态规划：

1. 
   
2. 设f(i,K)为a[i]到a[SIZEA]子序列中数组元素之和等于K的最小元素个数。
   
3. f的递推如下：
   
4. f(i,K)=1 if a[i]==K
   
5. f(i,K)=min{ f(i+1,K), 1+f(i+1,K-a[i]) }
   
6. 终止条件：
   
7. f(SIZEA,K)=1 if a[SIZEA]==K
   
8. f(SIZEA,K)=INFINITY otherwise
   
9. 题目就是求f(1,M)。
   

复制代码

[ 本帖最后由 emacsnw 于 2006-2-15 02:15 编辑 ]

fsilence

楼上的算法是完全正确的，非常感谢！

ArXoR

原帖由 win_hate 于 2/15/06 14:53 发表


这种方法求出来的总是连续和，是吗？ 或者我理解错了。

-_-......看错题目了