如何解决n为10 ^ 9的http://www.spoj.com/problems/MST1/

Question

使用从下至上的DP方法，我能够解决问题如何将http://www.spoj.com/problems/MST1/最多解决10 ^ 8。

如果输入很大，则n最高为10^9。我将无法创建最多10^9的查找表。那么有什么更好的方法来解决问题呢？

有启发式解决方案吗？

Answer 1

#include <iostream>
#include <climits>
#include <algorithm>

using namespace std;

int main()
{
    const int N_MAX = 20000001;
    int *DP = new int[N_MAX];
    DP[1] = 0;

    for (int i = 2; i < N_MAX; i++) {
        int minimum =  DP[i - 1];
        if (i % 3 == 0) minimum = min(minimum, DP[i/3]);
        if (i % 2 == 0) minimum = min(minimum, DP[i/2]);

        DP[i] = minimum + 1;
    }

    int T, N; cin >> T;
    int c = 1;
    while (T--) {
        cin >> N;
        cout << "Case " << c++ << ": " << DP[N] << endl;
    }

    delete[] DP;
}