1 1 vote How to prepare for Dynamic Programming topic in DAA for GATE exam? Algorithms algorithms dynamic-programming gate-preparation + – dan31 1.4k views answer comment Share Follow Print See 1 comment 1 1 comment reply Nishikant commented Oct 4, 2018 reply Follow flag 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 :) 3 3 replyShare Please log in or register to add a comment.
