具有给定和的子数组的计数，以便索引按升序排列

Question

给定一个数组，用给定的和计算子数组的数量，使索引按升序排列(它们不需要连续，但数组元素的索引应按升序排列。(

例如：数组-｛1 2 3 4 5｝，求和-5则{1,4}也是有效的子数组，因为索引是升序(1<4(。其他是{2,3}等

注意-这个问题似乎与子数组的计数问题非常相似，但当索引按升序排列时，它会变得更加复杂，因为那时会有更多的值。我请求有人分享一个相同的伪代码，如果不可能，分享逻辑。

Answer 1

这个问题相当于计算和为sum的子序列的数量。说指数必须上升并不意味着什么，只要你没有重复的指数。然后可以用背包式动态规划方法来解决这个问题。

定义dp[N+1][sum+1]以在dp[i][j]处存储数组的子序列数，直到(但不包括(索引i，其总和为j。Python代码如下：

N = 10
sum = 10
arr = [1,2,3,4,5,1,2,3,4,5]
dp = [[0 for x in range(sum+1)] for x in range(N+1)]
dp[0][0] = 1  # base case; one way to achieve a sum of 0 taking 0 elements
for i in range(N):
for j in range(sum+1):
if j + arr[i] <= sum:
dp[i+1][j+arr[i]] += dp[i][j]
dp[i+1][j] += dp[i][j]
print dp[N][sum]