How do I convert recursion into memoization or bottom up?

Question

int count(n){
 if(n==1) return 1;
 if(n%2==0)
  return 1+count(n/2);
 else 
  return Math.min(1+count(n+1),1+count(n-1));
 }

can you please explain how do I convert this code into dynamic programming? and if this can not be converted into can you please explain why. Else, is there any way to reduce the complexity of the program. Thank you.

Answer 1

I can offer the solution of your problem, using memoization and C++.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maximumSize=10;
void showContentVector1D(vector<int>& input)
{
    for(int i=0; i<input.size(); ++i)
    {
        cout<<input[i]<<", ";
    }
    return;
}
int count(int n, vector<int>& input)
{
    if(n==1)
    {
        input[n]=n;
        return input[n];
    }
    if(n%2==0)
    {
        input[n]=1+count(n/2, input);
        return input[n];
    }
    else
    {
        input[n]=min(1+count(n+1, input), 1+count(n-1, input));
        return input[n];
    }
    return input[n];
}
void solve()
{
    vector<int> memoization(maximumSize, -1);
    cout<<"Before, memoization <- ";
    showContentVector1D(memoization);
    count(7, memoization);
    cout<<endl<<"After, memoization <- ";
    showContentVector1D(memoization);
    cout<<endl;
    return;
}
int main()
{
    solve();
    return 0;
}

If we will perform the command-function count(7, memoization); with the number 7 and with the parameter memoization, therefore, the next output will appear:

Output:

Before, memoization <- -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 
After, memoization <- -1, 1, 2, 3, 3, -1, 4, 5, 4, -1,