Daily Coding Challenge with Solutions

Given a distance n, count total number  of ways to cover the distance with 1, 2 and 3 steps. Input: n = 4 Output: 7 Explantion: Below are the four ways  1 step + 1 step + 1 step + 1 step  1 step + 2 step + 1 step  2 step + 1 step + 1 step   1 step + 1 step + 2 step  2 step + 2 step  3 step + 1 step  1 step + 3 step // C++ program to count number of ways in DP  to cover a distance with 1, 2 and 3 steps  #include<iostream>  using namespace std;  int main() {      int n;     std::cin>>n;     int count[n+1];         // Initialize base values. There is one way to cover 0 and 1      // distances and two ways to cover 2 distance.     count[0]  = 1,  count[1] = 1,  count[2] = 2;         // Fill the count array in from bottom to up manner      for (int i=3; i<=n; i++)  ...

                                Dynamic Programming Introduction                                            Dynamic Programming is mainly an optimization over plain recursion . Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. For example, if we write simple recursive solution for Fibonacci Numbers , we get exponential time complexity and if we optimize it by storing solutions of sub problems, time complexity reduces to linear. Fibonacci Number using recursion and dynamic programming Let us start understand it with an example.  Let us take example as fib(4)  For fib(4),  fib(0) will called  twice ,  fib(1) will be called  thrice  ,  fib(2) will be called  twice, fib(3) will be cal...