HackerRank Dynamic Programming Quiz-2

Among the two approaches of dynamic programming Bottom Up is better for large problems as it does not lead to stack overflow.

 

The space complexity of Dynamic Programming is 0(n)

The time complexity of Dynamic Programming is 0(n)

 

The dynamic programming is more efficient than recursion when the space of the subproblems is less.

We use dynamic programming because referring to the previous solution output is cheaper than recomputing in terms of CPU cycles.

 Stage-subproblem of problem

ii:)State:-each stage has several states associated with it

iii:)Decision-it is taken at each stage

Optimal Policy in Dynamic Programming is a rule which determines the decision at each stage. A policy is called optimal if it is globally optimal

Steps involved:-

i:)Characterize structure of optimal solution

ii:)Recursively define the value of optimal solution

iii:)Compute value of optimal solution

iv;)Construct the optimal solution for entire problem