Intro to Dynamic Programming

Hey folks, Today I planned to something I don’t have much expertise in. Dynamic Programming.

Dynamic Programming is a technique for solving complex problems. It begins by splitting the complex problem into collection of similar sub problems. The next step is to solve these sub problems and stored in order to avoid repetitive computations.

One likely example of Dynamic Programming is Fibnoacci series. Fibonacci series is a sequence of numbers that follows the following rule

F(n) = F(n-1)+F(n-2)

This is the fibonacci sequence

0 1 1 2 3 5 8 13 …

As per definition of dynamic programming we can split the nth fibonacci number into sub sequence of n-1 and n-2 fibonacci numbers.

Fibonacci Series Construction

But the problem here is Fib(1) is required at multiple levels. So the number of re computations would be huge. So to avoid that comes the second step storing of already computed sub problems.

By storing the sub problem results we can reduce the number of computations and solve the problem quickly.

Okay we have seen enough about fibonacci series Let’s solve a real dynamic programming problem.

Climbing Stars:

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Since we are seeing dynamic programming today, I will skip directly to dynamic programming approach.

Understandings:

1. At each step the user can take 1 step upward or 2 step upward. So the final step can be either 1 or 2.
2. And the initial steps, if number of steps =1 there is only one way to reach top.
3. And if number of steps is 2 there is 2 ways to reach the top ( 2 steps at a time or 1 step at a time).
4. Initialize them in the store array.
5. Going backwards until all number of steps is 1 or 2 recursively call the function in the following manner.

NumberofWaystoReachTop = climbingStairs(numberOfSteps-1,store)+climbingStairs(numberOfSteps-2,store);

This will return the number of ways to possibly reach the top.

#100DaysofCode #Day16