# FLAASH - Editorial

Author: Varun Singh

SIMPLE

DP

### PROBLEM:

Given a number n, count minimum steps to reach 1 according to the given criteria.

### EXPLANATION:

One can think of greedily choosing the step, which makes n as low as possible and continue the same, till it reaches 1. If you observe carefully, the greedy strategy doesn’t work here.

Eg: Given n = 10 , Greedy --> 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1 ( 4 steps ).

But the optimal way is --> 10 -1 = 9 /3 = 3 /3 = 1 ( 3 steps ).

So, we need to try out all possible steps we can make for each possible value of n we encounter and choose the minimum of these possibilities.

It all starts with recursion.
F(n) = 1 + min{ F(n-1) , F(n/2) , F(n/3) } if (n>1) , else 0 ( i.e., F(1) = 0 )

We notice in the recurrence relation that the problem exhibits the property of overlapping subproblems and optimal substructure, so DP.

``````#include <bits/stdc++.h>
#define sz (int)1e6
using namespace std;
int getminsteps(int n, int *memo)
{
if( n == 1) return 0;                   // Base Case
if( memo[n] != -1)  return memo[n];     // Solved it. Return ans
int r = 1 + getminsteps(n-1,memo);      // Regular steps. From n to n-1
if(n%2 == 0)
r = min(r,1+getminsteps(n/2,memo));   // Divisible by 2 steps
if(n%3 == 0)
r = min(r,1+getminsteps(n/3,memo));   // Divisible by 3 steps.
memo[n] = r;                            // Save the result. If we forget this, then plain recursion
return r;
}
int main()
{
int t,n,i,ans;
cin >> t;
int memo[sz];                       // DP
memset(memo, -1, sizeof(memo));     // Fill all elements with -1 i.e not solved yet
while (t--)
{
cin >> n;
ans = getminsteps(n,memo);
cout << ans << endl;
}
return 0;
}
``````

### AUTHOR’S SOLUTIONS:

Author’s solution can be found here.