LeetCode 818. Race Car
문제풀이
기억화 검색.이 문제는 분명히 하위 문제로 고려될 수 있다.대체적인 사고방식: dp[n]를 설정하여 n의 가장 짧은 코드에 도달하기 위해 직접 A에서 가장 짧은 위치는 1, 3, 7, 15,..., (2^n)-1을 설정하면 분명히 고려해야 할 상황은 target이 2^(n-1)-1~(2^n)-1사이에 위치하고 이 구간을 어떻게 처리하는가이다.두 가지 방법.
4
dp[target] = dp[ (2^n) -1 - target] + n+1//+1
4
for m=0-> n-1:
dp[target] = min( dp[target],
dp[ target - (2^(n-1) -1 ) +(2^m -1) ] + n+m+1 )
코드에서 돌아가는 쓰기 방식을 실현하는 데 주의하십시오.
Code int f[10001]={0};
int racecar(int t) {
if(f[t]>0) return f[t];
int n = floor(log2(t)) +1;
if((1<<n) == t+1) f[t] = n;
else{
f[t] = racecar( (1<<n) - 1 - t) + n+1;
for(int m=0;m<n-1;m++){
f[t]=min(f[t], racecar( t - (1<<(n-1)) +(1<<m) )+n+m+1);
}
}
return f[t];
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)
이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
int f[10001]={0};
int racecar(int t) {
if(f[t]>0) return f[t];
int n = floor(log2(t)) +1;
if((1<<n) == t+1) f[t] = n;
else{
f[t] = racecar( (1<<n) - 1 - t) + n+1;
for(int m=0;m<n-1;m++){
f[t]=min(f[t], racecar( t - (1<<(n-1)) +(1<<m) )+n+m+1);
}
}
return f[t];
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
