title: The UVa 3n + 1 in C++ with Dynamic Programming
body: <p>So, there are ways to do this, and/or optimize this. Stupid that I am, I immediately wants to implement a recursive function, which later caused a segmentation fault, and then I tried to adopt dynamic programming, and it seemed to work, but somehow I got Wrong answer.</p>
  
  <p>Problem <a href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=3&amp;page=show_problem&amp;problem=36" rel="nofollow">Here</a></p>
  
  <p>So here's my code, and I think it's pretty self-explanatory.</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  using namespace std;
  
  int cycleLength(long long int);
  
  int cycleLengthResult[1000000];
  
  int main(int argc, char *argv[])
  {
      int i = 0, j = 0, cur = 0, max = 0;
      while ( cin &gt;&gt; i &gt;&gt; j )
      {
          if ( i &gt; j ) //swap to ensure i &lt;= j
          {
              int s = i;
              i = j;
              j = s;
          }
          for ( int k = i ; k &lt;= j ; ++ k )
          {
              cur = cycleLength(k);
              if (cur &gt; max) max = cur;
          }
          cout &lt;&lt; i &lt;&lt; " " &lt;&lt; j &lt;&lt; " " &lt;&lt; max &lt;&lt; endl;
          max = 0;
      }
  }
  
  int cycleLength(long long int arg)
  {
      if ( arg &gt; 1000000 ) //if out of array bound, then don't memorize, just calculate
      {
          if (arg % 2 == 0)
          {
              return 1 + cycleLength(arg/2);
          }
          else
          {
              return 1 + cycleLength(arg*3+1);
          }
      }
      if (!cycleLengthResult[arg-1]) //if result for arg doesn't exist then....
      {
          int valueForArg = 0;
          if (arg == 1)
          {
              valueForArg = 1;
          }
          else if (arg % 2 == 0)
          {
              valueForArg = 1 + cycleLength(arg/2);
          }
          else
          {
              valueForArg = 1 + cycleLength(arg*3+1);
          }
          cycleLengthResult[arg-1] = valueForArg;
      }
      return cycleLengthResult[arg-1];
  }
  </code></pre>
  
  <p>I passed all the sample inputs, and also (1, 1000000) for speed test. But it seemed that it's not the problem.</p>
  
  <p>I want to fix my code, and not change the methodology used, of course, I can just not use recursive, and use a loop instead in main, which wouldn't overflow. But it's fun.</p>