Участник:Gerakir/Leet Coding/Race Car

Материал из DISCOPAL
Перейти к: навигация, поиск

818. Race Car

class Solution {
public:
    map<int, int> step;
    int racecar(int finish) {
        int n = 1;
        int res = INT_MAX;
        if(finish == 0) return 0;
        if(step.find(finish) != step.end()) return step[finish];
        if((1 << 30) % (finish + 1) == 0) return log2(finish + 1);
        for(int n = 1; n <= log2(finish) + 1; n++) {
            int pos1 = pow(2, n) - 1;
            if(pos1 > finish/2 && pos1 < 2 * finish) {
                int tmp = INT_MAX;
                if(pos1 > finish)
                    tmp = n + 1 + racecar(pos1-finish);
                else {
                     int d, pos2;
                     for(int i=0; i<n; i++) {
                         d = pow(2, i) - 1;
                         pos2 = pos1 - d;
                         tmp = min(i + n + 2 + racecar(finish-pos2), tmp);
                     }
                }
                res = min(res, tmp);
            }
        }
        step[finish] = res;
        return step[finish];
    }
};