Количество подмассивов с заданной суммой, чтобы индексы находились в порядке возрастания

Question

Для данного массива подсчитайте количество подмассивов с заданной суммой, чтобы индексы находились в порядке возрастания (они не должны быть непрерывными, но индексы элементов массива должны быть в порядке возрастания. )

Например - Array - {1 2 3 4 5}, Sum - 5 Тогда {1,4} также является допустимым подмассивом, так как индексы расположены в порядке возрастания (1 <4). Другие: {2,3} et c. </p>

ПРИМЕЧАНИЕ. - Этот вопрос, по-видимому, очень похож на вопрос подсчета подмассивов, но он становится более сложным, когда дело доходит до индексов в порядке возрастания, поскольку тогда будет больше значений. Я прошу кого-нибудь, пожалуйста, поделитесь псевдокодом для того же самого и, если это невозможно, поделитесь логи c.

Answer 1

Эта задача эквивалентна подсчету числа подпоследовательностей, которые составляют sum. Сказать, что индексы должны возрастать, на самом деле ничего не значит, если у вас нет повторяющихся индексов. Тогда проблема может быть решена с помощью метода рендеринга c в стиле рюкзака.

Определите 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]