문자열 s가 있다고 가정합니다. s는 0 - 9 사이의 숫자를 포함하고 또 다른 숫자 k도 있습니다. s가 [1, k]의 숫자 목록으로 표현될 수 있는 다양한 방법을 찾아야 합니다. 답이 매우 크면 결과 모드 10^9 + 7을 반환합니다.
따라서 입력이 s ="3456" k =500과 같으면 출력은 [3, 4, 5, 6], [34, 5, 6], [3, 4, 56], [3, 45, 6], [34, 56], [345, 6], [3, 456]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
m :=10^9 + 7
-
N :=s
의 크기 -
dp :=크기 목록(N + 1) 및 0으로 채우기
-
dp[N] :=1
-
N − 1에서 0까지의 범위에 있는 i에 대해 1만큼 감소합니다.
-
curr_val :=0
-
i에서 N 범위의 j에 대해 수행
-
curr_val :=curr_val * 10 + (s[j]를 숫자로)
-
curr_val이 1~k 범위에 있으면
-
dp[i] :=(dp[i] + dp[j + 1]) 모드 m
-
-
그렇지 않으면
-
루프에서 나오다
-
-
-
-
반환 dp[0]
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class 솔루션:def solve(self, s, k):m =10 ** 9 + 7 N =len(s) dp =[0] * (N + 1) dp[N] =1 for i in range(N − 1, −1, −1):curr_val =0 for j in range(i, N):curr_val =curr_val * 10 + int(s[j]) if 1 <=curr_val <=k:dp[ i] =(dp[i] + dp[j + 1]) % m else:break return dp[0]ob =Solution()s ="3456"k =500print(ob.solve(s, k))입력
"3456", 500출력
7