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

Question

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

例如 - Array - {1 2 3 4 5}, Sum - 5 那么 {1,4} 也是一个有效的子数组，因为索引按升序排列 (1 < 4)。其他是 {2,3} 等。

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

标签： arraysdynamic-programmingsub-array

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]