memoization in dynamic programming

Question

can please tell me how memoization is working in this dp example. dp example problem, codechef

the part where i stuck is like when input is 4 then why code is calculating n-1 i.e 4-1 when optimal step would be 4/2 or for input =10 why we will calculate n-1 till 1. Any help would be appreciated. New to dynamic programming so please bear with me.

Please don't simply provide links to relevant resources. Get the essence into your question. There are two solutions to your problem: "(4 - 1) / 3 = 1" and "4 / 2 / 2 = 1". As for the question itself, this topic [here](https://stackoverflow.com/questions/1065433/what-is-dynamic-programming) amongst others — , Jan 03 '17 at 19:03

score 0 · Answer 1 · answered Jan 03 '17 at 19:02

Memoization in dynamic programming is just storing solutions to a subproblem. for input n=4 you calculate its solution. So you try step 1. Subtract 1 + the solution to the subproblem n=3. For this to evaluate you need to solve the problem n=3, because you have not solved it previously. So you again try step 1 until you get to the base problem of n = 1 where you output 0.

After you tried step 1 for the current problem you try step 2 which means dividing n and afterwards you try step 3. You try every step for every subproblem, but because you store the best value at every subproblem you can use this when it occurs again.

For example when you get back to n=4 after you tried step 1 on it you try step 2 on it and you see that you can use n / 2 and because you already calculated the optimal value for n=2 you can output 1 + optimal value for n=2 which is 1, so in total 2.

score 0 · Answer 2 · answered Jan 03 '17 at 19:24

The link explains it fairly clearly. If F(n) is the minimal number of steps to convert n to 1, then for any n > 1 we have the following recurrence relation:

F(n) = 1 + min(F(n-1), F(n/2), F(n/3)) // if n divisible by 2 and 3
F(n) = 1 + min(F(n-1), F(n/2))         // if n divisible by 2 and not 3
F(n) = 1 + min(F(n-1),         F(n/3)) // if n divisible by 3 and not 2
F(n) = 1 +     F(n-1)                  // all other cases

For your case, n=4, we have to compute F(n-1) and F(n/2) to decide which one is minimum.

As for the second question, when n=10 we will evaluate first F(9). During this evaluation all values F(8), F(7), ... F(2)are computed and memoized. Then, when we evaluate F(10/2) = F(5) it will be simply a matter of looking up the value in the array of memoized values. This will save lots of computing.

score 0 · Answer 3 · answered Jan 03 '17 at 22:44

May be you can do as follows in JS;

function getSteps(n){
  var fs = [i => i%3 ? false : i/3, i => i%2 ? false : i/2, i => i-1],
     res = [n],
     chk;
  while (res[res.length-1] > 1) {
    chk = false;
    fs.forEach(f => !chk && (chk = f(res[res.length-1])) && res.push(chk));
  }
  return res;
}
var result = getSteps(1453);
console.log(result);
console.log("The number of steps:",result.length);

memoization in dynamic programming

3 Answers3