시간 제한 초과 알고리즘의 오류

Question

3의 나눗셈으로 숫자를 변환하고 싶습니다.

숫자는 숫자가 같고 앞에 0이없는 다른 숫자로 변환 될 수 있습니다.

숫자를 다른 숫자로 변환하는 비용은 해당 숫자의 절대 차이의 합입니다. 예를 들어, 235에서 331로 변환하는 비용은 5입니다 (해당 자릿수의 절대 차이는 | 3 || + | 3-3 | + | 1-5 |이므로 | 1 | + 0+ | -4 |

Number= 66 cost= 3 

36,45,54,57,63,66,69,75,78,87,96이다 (66)의 선정 ≤3 내에서 생성 될 수있는 번호 = 5.

. 그래서 재귀 호출을 사용 내가 문자열로 입력을 복용하고
및 가하는 모든 조합

: 대답은 11

내 접근 방식3210

public static void cal(int len , int sum , int c , String SS){ if(c>cost) return ; if(len==SS.length()){ if(sum%3==0) ans++; return; } for(int i=0;i<=9;i++){ int xx =Math.abs(i-Character.getNumericValue(SS.charAt(len))); cal(current+1, len+1, sum+i, c+xx, SS); } } 

MSB에서는 0이 허용되지 않으므로.

어떻게 내가 내 알고리즘을 향상시킬 수있는 예 237946732463272737 60 내 코드는 특정 시간에 계산하지이 출력의

for(int i=1;i<=9;i++){ 
    int xx =Math.abs(i-Character.getNumericValue(SS.charAt(0))); 
    cal(i, 1, i, xx , SS); 
} 

이 내가 문제를 해결하는 방법입니다

Answer 1

: 당신은 DP [P] [C 필요 [S]DP가 [I] [j]가 [K]를 당신이 J 금액 지금까지 합까지가있는 숫자의 수치 표현 위치 I되도록 지정 어레이 k. 기본 아이디어는 문제가 하위 문제 (왼쪽 숫자, 왼쪽 돈, 전체 합계)로 변경되는 숫자를 변경하거나 (없는 경우) 각 숫자에 최대 10 개의 옵션이 있으므로 각 상태를 채우기 위해 루프가 필요할 것입니다. 10. 그래서 시간 복잡성 O (P * C * S * 10). N은 최대 P = 19 (자릿수)에서 최대 10^18에 불과하므로 C = 200 (언급 한대로)이고 S는 최대 9 * 18 (자릿수의 합)입니다. 따라서이 알고리즘은 주어진 시간 제약과 메모리가 O (P * C * S) 인 경우 괜찮습니다.
그래서 재귀 논리 이외에도 재귀와 함께 메모 (이미 방문한 상태에 대한 답변 저장)를 사용해야합니다.

Answer 2

이와 같은 문제가 발생하면 모든 가능성을 생성하기 위해 재귀를 사용하면 입력 크기가 커짐에 따라 기하 급수적으로 증가하는 데 시간이 걸립니다. 큰 입력 크기에 대해이를 빠르게 수행하는 알고리즘을 원할 경우 모든 가능성을 생성하지 않고 계산하는 방법을 생각해 보는 것이 좋습니다.

당신은 3로 나누어 다수의 숫자의 합이 그래서 아마도 원래 번호의 숫자의 합이 모듈 3을 제공 무엇을 참조 3.

으로도 나눌 수 있다는 사실을 원하는 아마 것입니다. 예를 들어 1 일 경우, 숫자 값의 총 변경은 2 모듈로 3이되어야합니다. 그러면 거기에서 진행할 수 있습니다.