Advanced Search

Using a Map for Dynamic Programming in C++

/ Published in: C++
Save to your folder(s)
Really DP-lite. Memoize the solution for a recursive problem so it can be looked up on subsequent iterations.

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. #include <iostream>
  2. #include <map>
  3. using namespace std;
  4.  
  5. int main() {
  6.     map<int, int> results;
  7.     map<int, int>::iterator it;
  8.     int i, j, x, temp;
  9.     int cycles = 1;
  10.     int maxcycles = 0;
  11.     while (cin >> i >> j) {
  12.         cout << i << " " << j << " ";
  13.         if (i > j) {
  14.             temp = i;
  15.             i = j;
  16.             j = temp;
  17.         }
  18.  
  19.         for (; j >= i; --j) {
  20.             x = j;
  21.             it = results.find(x);
  22.             if (it == results.end()) {
  23.                 while (x != 1) {
  24.                     if (x % 2 != 0) {
  25.                         x = (3*x) + 1;
  26.                     } else {
  27.                         x /= 2;
  28.                     }
  29.                     ++cycles;
  30.                 }
  31.                 results.insert(pair<int, int>(j, cycles));
  32.             } else {
  33.                 cycles = it->second;
  34.             }
  35.             if (cycles > maxcycles) maxcycles = cycles;
  36.             cycles = 1;
  37.         }
  38.  
  39.         cout << maxcycles << endl;
  40.         maxcycles = 0;
  41.         cycles = 1;
  42.     }
  43.  
  44. 	return 0;
  45. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.