TCS Digital Dynamic Programming Quiz- 2

 Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer , if it has not been solved, solve it and solve the answer. This is usually easy to think of  and very intuitive. This is referred to as memoization. Mean it follows the top down approach

Analyze the problem and see the order in which the sub problems are solved and start solving from the trivial subproblem ,up towards the given problem. It is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic problem

 First item A will be selected as it will contribute maximum profit among all the elements.

After selecting A, mo more item will be selected. Hence,for this given set of item total profit is 24 whereas, the optimal solution can be achieved by selecting item ,B and C, where the total profit is 18+18=36

Optimal substructure and Overlapping subproblem both are the property of the dynamic programming

 Overlap sub problem is a property in which value of a subproblem is used several times

The top down approach uses memoization technique which store the previous calculated values. Due to this, the time complexity is decreased  but the space complexity is increased.

 All the problem except fractional knapsack problem

 Longest common subsequence problem has both Optimal substructure and overlapping subproblem. Hence dynamic programming should be used to solve this problem

The huffman coding takes O(nlogn) time to complete their solution

 (A,D)=7 (First minimum weightage edge from A that connect edge D )

(A,B)=10 (Now from A second minimum edge that connects edge B)

(D,F)=22 (Now from D there is minimum edge which connects edge F )

(F,C)=4 (Now from F there is minimum edge which connects edge C )

(F,G)=5 (Now from F  there is minimum edge which connects edge G )

(G,E)=2 (Now from G there is minimum edge which connects edge E)

So all the vertices are cover and the above sequence is followed to find the MST.