Dynamic Programming 04 - Framework for solving DP problem

Lecture 04 - Framework for solving Dp problem

: Solve Dp basic problems & outline the basic steps required for a dynamic programming solution

 

Recap ch.3) Idea of DP

n = 5

1 + 2 + 3 + 4 + 5

f(n) = f(n-1) + n

[0,1,3,6,10,15]

*Core Idea of Dp : we don't want to recalculate things.

We want to rely on existing solutions on the information that we already know.

What if n = 6?

sum = f(6) = f(5) + 6 = 15 + 6 = 21

Just add 6 to f(5)!

→ this technique is "Memoization" (cached results)

: we cache the result of a computation so we can use it later

= optimize the time complexity by giving space

"Time memory trade-off"

 

Example : Climbing stairs problem(more real problem)

Goal : There's a staircase and answer the question in how many distinct ways can you climb to the top.

 

*We are given a staircase of size n, and there's contraint you can either climb one or two steps at time.

→ we need total number of ways to get to the top of the stair case

*one step = small step, two step = one jump

1st way : four small step - one step at a time 

                1 1 1 1

2nd way : small step, one jump, another small step

                 1 2 1

3rd way : 2 1 1 

4th way : 1 1 2 

Last way : 2 2  

→ total 5 ways

 

Solve

1. Express our goal as an "objective function"

objective function : function that you want to minimize or maximize in your problem for instance

eg) cost → minimize, profit  → maximize

In our case, objective function is the distinct number of ways to reach to a certain stair → it's minimization problem.

f(i) is the number of distinct ways to reach the i-th stair

+) it's always good idea to write down your objective function, defining the objective function is most 50% of the solution.

 

2. Break the problem down into simpler sub problems and identify the base cases

n = 2 (only have 2 staircases)

f(2) = 2 (1st way : 1 1, 2nd way : 2)

f(1)  = 1 (1st way : 1)

the smallest sub problem (don't have a stair at all)

f(0) = 1 (doing nothing also weight as count)

 

3. Write down the recurrence relation for the optimized objective function

"Recurrence relation" :

Sometimes you can spot the pattern by solving the problem for a few more input values.

Find f(3), f(4), f(5) ... notice certain pattern 

→ devise the formula in this case.  

→ sometimes it's hard

Let's find formula in this case

: Assume we are at the top of staircase from where coould we get here.

 

How do we know the total number of ways?

We need to add this two guys (n-1, n-2) together.

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

In combinatorics, it is called the rule of sum or addition principle.

 → Idea : If we have A ways to do something and B ways of doing something 

               and we cannot do both of those things at the same time,

               then there are A plus B ways to choose one of the actions.

In our case, we always choose either to make one step or two steps which is why we can apply the rule of sum.

We have two disjoint set and we apply the Union operation.

*Recurrence relation is basically the transition function.

It's the function that allows you to transition from one subproblem to the other subproblem.

 

4. Order of computation

: we need to determine the order in which sub problems are solved.

In our case, we rely on the problem that we were just solving (n-1 and n-2).

So we have cerain order here. 

We need to calculate smaller and valuest first.

 

5. Location of the answer

: Where we are looking for the answer

In our case, the answer is in f(n).

 

Code

/*

1. Define the objective function

f(i) is the number of distinct ways to reach to the i-th stair.

2. Identify base cases

f(0) = 1

f(1) = 1

3. Write down a recurrence relation for the optimized objective function.

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

4. What's the order of execution?

bottom-up because we always rely on the values from the two previous subproblems

5. Where to look for the answer?

f(n)

*/

// Time complexity : O(n) we need to go over all tje stairs

// Space complexity : O(n) we allocate an array of size n+1

func climbStair (int n) {

    int dp [n+1];

    dp[0] = 1;

    dp[1] = 1;

    for(i=2; i<=n; i++){

          dp[i] = dp[i-1] + dp[i-2]

    }

    return dp;

  }

 

https://www.youtube.com/watch?v=QlT4HG93Gaw