假设有一个无限长的x轴，你站在原点x=0处

题目

假设有一个无限长的x轴，你站在原点x=0处，要去往的目标是x轴上的任意一个整数点。但是每次移动，只能向左或者向右，而且第N次移动就移动N的距离。现给定一个目标点target，要求为了到达目标点，移动的最少次数。

示例

target=3，则最少移动2次：第一次到1，第二次到3；
target=2，则最少移动3次：第一次到1，第二次到-1，第三次到2。

输入

整数N，表示要到达的目标点；

输出

整数n，最少需要移动的次数。

代码

#include <iostream>
#include <vector>
#include <cmath>
#include <map>

using namespace std;

map<int, map<int, bool> > dp;

bool is_ok(int target, int n_step) {
    if ((1 + n_step) * n_step / 2 < abs(target)) return false;
    if (n_step < 0) return false;
    if (0 == n_step && 0 == target) return true;

    auto it = dp.find(target);
    if (it != dp.end() && it->second.find(n_step) != it->second.end()) {
        return dp[target][n_step];
    }
    
    dp[target][n_step] = is_ok(target - n_step, n_step - 1) 
                || is_ok(target + n_step, n_step - 1);
    return dp[target][n_step];
}

int main() {
    int N; cin >> N;
    for (int i = 1; i <= 2*N; ++i) { 
        if (is_ok(N, i)) { cout << i; return 0; } 
    }

    return 0;
}