문제풀이

기억화 검색.이 문제는 분명히 하위 문제로 고려될 수 있다.대체적인 사고방식: dp[n]를 설정하여 n의 가장 짧은 코드에 도달하기 위해 직접 A에서 가장 짧은 위치는 1, 3, 7, 15,..., (2^n)-1을 설정하면 분명히 고려해야 할 상황은 target이 2^(n-1)-1~(2^n)-1사이에 위치하고 이 구간을 어떻게 처리하는가이다.두 가지 방법.
4

target의 뒷머리 위치(2^n)-1까지 간다. 이때 고개를 돌려 뒤로 가면 더 가야 할 최단 걸음 수가 적당하다=뒷머리 위치와 target의 차이dis의 dp[dis].뒤로 이동하는 것은 이전에 이동한 등장거리의 소모 걸음 수와 같다

dp[target] = dp[ (2^n) -1 - target] + n+1//+1   

4

target에 도착하기 전 위치 2^(n-1)-1, 이때도 고개를 돌려 0-n-1걸음을 순서대로 고려하고 새로운 기점에서 target까지의 거리를 고려한다

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];
    }