Read a good C++ book first - or you will not know many details 


2 things I derived from it:


    

  1. learn details of C++ - read good book
    2. 

  2. don't copy someone functions like i copied min (macro)
    3. 



Sometime little details that I don't know can cause lots of time wasted:
if you use macro definition like below : min , it causes the program to call getmin steps TWICE!
i did not know that!
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std ;
#define min(a,b) ( (a) < (b) ? (a) : (b))

int memo[10 + 1] ;



void reset_memo()
{
    cout << endl ;
    cout << "RESETTING MEMO" << endl ;
    for (int i = 0 ; i < 11 ; i++) {
        memo[i] = -1 ;
    }
}

int getMinSteps(int n)
{
    cout << "======current n : " << n <<  " ===============" << endl ;
    if (n == 1) {
        cout << "BASE CASE n = 1 and returning 0..." << endl ;
        return 0;
    }  // base case

    if (memo[n] != -1) {
        return memo[n];
    } // we have solved it already :)

    cout << "STEP 1 " << endl ;
    int r = 1 + getMinSteps(n - 1);    // '-1' step .  'r' will contain the optimal answer finally

    if (n % 2 == 0) {
        cout << " STEP 2: "  << endl ;
        int v =  getMinSteps(n / 2); // <--- so getMinSteps will be called only once!
        r = min(r , 1 + v) ;
    }  //  '/2' step

    if (n % 3 == 0) {
        cout << " STEP 3: "   << endl ;
        r =  min(r , 1 + getMinSteps(n / 3)) ;
    }  //  '/3' step

    memo[n] = r ;  // save the result. If you forget this step, then its same as plain recursion.
    return r;
}

int main(){
    reset_memo();
    getMinSteps(2);
    getchar();
    getchar();

}
Posted by