퍼뮤 테이션을 풀기위한 동적 프로그래밍

Question

4 자리 "1", "2", "3", "4"가 있습니다.

프로그램 입력은 위의 4 자리 숫자 만 포함 할 수있는 정수입니다. 많은 의견이있을 것입니다. 입력

예 : 1123, 4123, I는 다음과 같은 규칙을 준수 주어진 입력의 순열의 수를 계산하기 위해 필요한 4444

:

1. 어떤 유사한 두 자리에 인접 없어야을 서로. 예 : 1223은 허용되지 않지만 2123은 허용됩니다.
2. 시작 끝자리 숫자가 같아서는 안됩니다. 그들은 원형으로 인접한 것으로 간주됩니다. 예 : 2132는 허용되지 않습니다.
3. 입력 값이 4 자리이면 결과 순열 길이는 4 자리이어야합니다.

이 문제를 해결하기 위해 모든 종류의 메모를 사용할 수 있습니까? 어떻게 그것을 2 차원 어레이에 저장합니까? 팁을 주셔서 감사합니다!

Answer 1

허용되는 계약 수에만 관심이 있으므로 대부분의 입력은 동일한 결과를 가져옵니다.

• 자릿수
• 전용 주파수 분포는 중요하지 않고, 입력에 숫자의 순서, 즉 1,123 및 그 대답 1,223 리드 중요하다. 자리 주파수에 따라 입력을 분류

는 4 개 자리 입력에 대해 단지 5 가지 경우로 연결 :

class  examples 
4   4444, 2222, ... 
3 1  1211, 2232, ... 
2 2  1331, 4422, ... 
2 1 1  3413, 1123, ... 
1 1 1 1 1234, 4231, ... 

각 경우에 대한 답을 알아 낸 후, 새로운 입력은 매우 빠르게 처리 할 수 ​​있습니다 .