阿里编程测试

对，就是HashMap<sum, count> //sum表示和，count表示这个sum一共有多少种组合数。

可以用动态规划做。

动态规划要怎么做？ 【 在 NachtZ 的大作中提到: 】 : 可以用动态规划做。

dp[2][sum]，sum表示的是可能的和，dp的值是在第i条的结果中，所有可能sum的组合的数量。然后从第一条开始扫描，扫到最后一条记录。两个一维数组分别代表前i条记录和第i+1条记录。已知第i条记录，然后根据第i条记录对应的dp数组和第i+1条的数值rec[i+1]求第i+1条的。 设记录数组是rec。转移公式是 ``` dp[1][rec[i+1]]++ for i:=1;i<=n;i++{ dp[1][sum] = dp[0][sum-rec[i+1]]+ dp[0][sum] } ``` 大致公式就是这样，实际写的话，可能还有些边角要改改。 然后最后的结果就是dp[len(rec)][n]。 【 在 ABs 的大作中提到: 】 : 动态规划要怎么做？

rec[n+1]? 【 在 NachtZ 的大作中提到: 】 : [md] : dp[2][sum]，sum表示的是可能的和，dp的值是在第n条的结果中，所有可能sum的组合的数量。然后从第一条开始扫描，扫到最后一条记录。两个一维数组分别代表前n条记录和第n+1条记录。已知第n条记录，然后根据第n条记录对应的dp数组求第n+1条的。 : 设记录数组是rec。转移公式是 : ...................

(⊙o⊙)…字母重复了，我改下... 【 在 trumpet 的大作中提到: 】 : rec[n+1]?

n是什么啊，代码看起来很神奇的样子 【 在 NachtZ (http://nachtz.top/) 的大作中提到: 】 : [md] : dp[2][sum]，sum表示的是可能的和，dp的值是在第i条的结果中，所有可能sum的组合的数量。然后从第一条开始扫描，扫到最后一条记录。两个一维数组分别代表前i条记录和第i+1条记录。已知第i条记录，然后根据第i条记录对应的dp数组和第i+1条的数值rec[i+1]求第i+1条的。 : 设记录数组是rec。转移公式是 : ...................

额。n是题目中给的符号啊。表示对所求的和。之前没认真看题目，没注意到重了。 【 在 trumpet ( trumpet) 的大作中提到: 】 : n是什么啊，代码看起来很神奇的样子

【 在 myth2016 的大作中提到: 】 : 首先定义一个a[k]，的数组记录和为k 的组合数，从第一个数m开始，如果大于就丢弃。否则，对于任意一个a[a[i]+m]加1，一直计算，好像就可以了。这样的话复杂度就是O(n+k）