PROBLEM LINK:
Author: Varun Singh
DIFFICULTY:
SIMPLE
PREREQUISITES:
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.