Using A Map For Dynamic Programming In C++

Roger Turnau

Nov. 04, 08 · Code Snippet

2.8K Views

// A solution to the "Three N + 1" Problem for the UVa Online Judge
// The difference between the DP solution and the brute-force solution is dramatic -- 
// a run-time of 1.030 seconds drops to 0.370 


#include 
#include 
using namespace std;

int main() {
    map results;
    map::iterator it;
    int i, j, x, temp;
    int cycles = 1;
    int maxcycles = 0;
    while (cin >> i >> j) {
        cout << i << " " << j << " ";
        if (i > j) {
            temp = i;
            i = j;
            j = temp;
        }
        
        for (; j >= i; --j) {
            x = j;
            it = results.find(x);
            if (it == results.end()) {
                while (x != 1) {
                    if (x % 2 != 0) {
                        x = (3*x) + 1;
                    } else {
                        x /= 2;
                    }
                    ++cycles;
                }
                results.insert(pair(j, cycles));
            } else {
                cycles = it->second;
            }
            if (cycles > maxcycles) maxcycles = cycles;
            cycles = 1;
        }
        
        cout << maxcycles << endl;
        maxcycles = 0;
        cycles = 1;
    }
	
	return 0;
}

Dynamic programming

Opinions expressed by DZone contributors are their own.

Using A Map For Dynamic Programming In C++

Partner Resources

Comments

Likes