Dynamic Programming Preparation for Gate

Question

How to prepare for Dynamic Programming topic in DAA for GATE exam?

Comments

So to solve any problem using dynamic programming we need to make sure that we find this things in that problem

1)optimal substructure--->is there any substructure/subproblem present which can be used to solve the larger problems.

2)Recursive equation-->if such subproblems exists can we find out the recursive equations.

3)Repeating subproblems-->this is Most IMP,because as there will be overlapping subproblems/repeating subproblems so in dynamic programming we don't need to solve them again and again.we can just solve them once and store the result and whenever we come across that problem again we will just use the result.

So in gate if they give you any problem 1)first identify whether it is dynamic or not.

2)if it is dynamic then they may ask you to find out the time complexity--->so as you know there will be repeating problems similarly there will be unique problems-->so we need to solve only them--> so time complexity will always be-->  

How many unique subproblems are there * how much time it takes to each subprobelm

Hope that helps you :)