문제 설명
인덱스가 오름차순으로 정렬되도록 주어진 합계를 갖는 하위 배열의 개수 (Count of sub‑arrays with a given sum such that the indices are in ascending order)
주어진 배열에서 인덱스가 오름차순이 되도록 주어진 합계로 하위 배열의 수를 계산합니다(연속적일 필요는 없지만 배열 요소의 인덱스는 오름차순이어야 합니다. )
예: 배열 ‑ {1 2 3 4 5}, Sum ‑ 5 그러면 인덱스가 오름차순(1 <4)이므로 {1,4}도 유효한 하위 배열입니다. 기타는 {2,3} 등입니다.
참고 ‑ 이 질문은 하위 배열의 개수에 대한 질문과 매우 유사한 것처럼 보이지만 인덱스가 오름차순인 경우 더 복잡해집니다. 더 많은 값이 있으므로 주문하십시오. 누군가에게 동일한 의사 코드를 공유하고 가능하지 않은 경우 논리를 공유해 달라고 요청합니다.
참조 솔루션
방법 1:
This problem is equivalent to counting the number of subsequences that sum to sum. Saying the indices have to be ascending doesn't really mean anything, as long as you don't have repeating indices. Then the problem can be solved with a knapsack‑esque dynamic programming approach.
Define dp[N+1][sum+1] to store, at dp[i][j] the number of subsequences of the array up to (but not including) index i that sum to j. Python code is as follows:
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]
(by gamerrk1004、aeternalis1)