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.


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.