具有给定总和的子数组的计数，使得索引按升序排列

Question

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

例如，-Array-{1 2 3 4 5}，Sum-5 Then{1,4}也是一个有效的子数组，因为索引是按升序（1

注意——这个问题看起来非常类似于子数组的计数问题，但是当索引以升序排列时就变得更加复杂了，因为那时会有更多的值。我请求有人请分享同样的伪代码，如果不可能，分享逻辑。

Answer 1

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

定义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]