DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Roger has posted 34 posts at DZone. View Full User Profile

Using A Map For Dynamic Programming In C++

11.04.2008
| 5664 views |
  • submit to reddit
        // 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 <iostream>
#include <map>
using namespace std;

int main() {
    map<int, int> results;
    map<int, int>::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<int, int>(j, cycles));
            } else {
                cycles = it->second;
            }
            if (cycles > maxcycles) maxcycles = cycles;
            cycles = 1;
        }
        
        cout << maxcycles << endl;
        maxcycles = 0;
        cycles = 1;
    }
	
	return 0;
}