第三题我用回溯过了百分之三,超时了。看见你说用dp,感觉想明白了,用一个矩阵dij表示前i个数组元素能够拼凑出和为j的情况数(题目说了j最多500)。比如前三个元素能够拼凑出和为6的情况依赖于前两个元素能够拼凑出1至5的情况数。如果第三个元素是3的话,排除前两个元素拼凑出(6-3)的情况即可。
点赞 评论

相关推荐

牛客网
牛客网在线编程
牛客网题解
牛客企业服务