Python에서 k 크기의 증가하는 부분 수열의 수를 찾는 프로그램

<시간/>

nums라는 숫자 목록과 또 다른 값 k가 있다고 가정하면 엄격하게 증가하는 크기 k의 부분 시퀀스 수를 찾아야 합니다. 답이 매우 크면 10^9 + 7로 수정하십시오.

따라서 입력이 nums =[2, 3, 4, 1] k =2와 같으면 크기가 2인 하위 시퀀스가 있으므로 출력은 3이 됩니다. [2, 3], [3, 4], [2, 4].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m :=10^9 + 7
dp :=숫자와 크기가 같고 1로 채워지는 목록
다음 k번 반복, 수행
- dp - 1에서 0 사이의 범위 크기에 있는 j에 대해 1 감소, do
  - dp[j] :=0
  - 0~j 범위의 i에 대해 다음을 수행합니다.
    - 숫자[i] <숫자[j]이면
      - dp[j] :=dp[j] + dp[i]
return(dp의 모든 요소 합계) mod m

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, nums, k):
      m = 10 ** 9 + 7
      dp = [1] * len(nums)
      for _ in range(k - 1):
         for j in range(len(dp) - 1, -1, -1):
            dp[j] = 0
            for i in range(j):
               if nums[i] < nums[j]:
                  dp[j] += dp[i]
      return sum(dp) % m
ob = Solution()
nums = [2, 3, 4, 1]
k = 2
print(ob.solve(nums, k))

입력

[2, 3, 4, 1], 2