>source

c++에서 문제에 대한 해결책을 코딩하려고했습니다.

재귀 만 사용하여 해결해야합니다 모듈러스 10000000007은 문제가되지 않습니다

문제점 : Davis는 한 번에 각 계단 1, 2 또는 3 단계를 등반하는 것을 좋아합니다.

N 개의 계단 각각에 대한 각각의 높이가 주어지면 각 계단을 올라갈 수있는 방법의 수를 찾아 인쇄하고, 모듈로 10 ^ 10 + 7

예제 n= 5의 경우

계단에는 5 단계가 있습니다. DAVIS는 다음 단계의 순서 순서를 단계적으로 수행 할 수 있습니다.

1 1 1 1 1

1 1 1 2

1 1 2 1

1 2 1 1.

2 1 1 1

1 2 2

2 2 1

2 1 2

1 1 3.

1 3 1

3 1 1

2 3

3 2.

이 5 단계를 취할 수있는 13 가지 방법과 13 모듈러 10000000007= 13

지금까지 재귀를 사용하여 내 솔루션 :

int ways(int n) {
    if(n==1) return 1;
    if(n==2) return 2;
    if(n==3) return 4;
    return (ways(n-3)+ways(n-2)+ways(n-1))%10000000007;
}

code는 완벽하게 작동하지만 큰 계산에는 너무 오래 걸립니다. 최적화하는 방법이있는 경우 공유 할 수 있습니다. 해결책을 더 잘 늘리십시오. 감사 해요.

0의 값이 아닌 값을 가정 한 1 << (n -1)을 고려해 봤습니까?

Mgetz2021-09-10 15:37:02

그 재귀가 Fibonacci를 상기시켜 줍니까?

harold2021-09-10 15:38:32

모호성을 생각해보십시오. 또한 제한은 N 번째 전력을 초과하는 3 개가 초과 할 때만 재생됩니다.

500 - Internal Server Error2021-09-10 15:43:43

일부 배열에서는 주어진 x에 대한 return (x) 리턴을 추적합니다.

Marek R2021-09-10 15:45:23

또한 10000000007이 소수가 아닙니다. 그래서 작은 레버리지로 사용할 수있는 경우 피사 노 기간을 확인하는 것이 좋을 것입니다.

Marek R2021-09-10 15:49:42
  • 이전 android : Kotlin room 쿼리가 제 시간에 반환되지 않습니다
  • 다음 Cypress /JavaScript의 조건에 따라 요소를 선택하는 방법