i번째 점(0에서 n-1까지)이 위치 x =i에 있는 선에 n개의 점이 있다고 가정하면 각각 다음과 같이 겹치지 않는 정확히 k개의 서로 다른 선분을 그릴 수 있는 방법의 수를 찾아야 합니다. 세그먼트는 두 개 이상의 점을 포함합니다. 각 선분의 끝점에는 정수 좌표가 있어야 합니다. k개의 선분은 주어진 n개의 점을 모두 포함할 필요는 없으며 끝점을 공유할 수 있습니다. 답이 너무 크면 결과 모드 10^9+7을 반환합니다.
따라서 입력이 n =4 k =2와 같으면 출력은 5가 됩니다. 다섯 가지 가능성 [(0 to 2),(2 to 3)], [(0 to 1),(1 to 3)], [(0 ~ 1),(2 ~ 3)], [(1 ~ 2),(2 ~ 3)] 및 [(0 ~ 1),(1 ~ 2)]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- m :=10^9 + 7
- n :=n - 1
- dp() 함수를 정의합니다. 이것은 i, 덮은, j가 걸릴 것입니다
- i가 n과 같으면
- j가 k와 같으면 true를 반환하고 그렇지 않으면 false를 반환
- j> k이면
- ans :=dp(i + 1, False, j) + dp(i + 1, True, j + 1)
- covered가 사실이면
- ans :=ans + dp(i + 1, True, j)
- mod m으로 반환
- 메인 메소드에서 dp(0, False, 0)를 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(n, k): m = 10 ** 9 + 7 n -= 1 def dp(i, covered, j): if i == n: return j == k if j > k: return 0 ans = dp(i + 1, False, j) + dp(i + 1, True, j + 1) if covered: ans += dp(i + 1, True, j) return ans % m return dp(0, False, 0) n = 4 k = 2 print(solve(n, k))
입력
4, 2
출력
5