18C5T13 Study Guide - Final Guide: Dynamic Programming, Negative Cost, Travelling Salesman Problem

• School: Jawaharlal Nehru Technological University - JNTU Kakinada
• Department: Engineering
• Course: 18C5T13

Document Summary

Dynamic programming is a design principle which is used to solve problems with overlapping sub problems. It is used when the solution to a problem can be viewed as the result of a sequence of decisions. It avoid duplicate calculation in many cases by keeping a table of known results and fills up as sub instances are solved. In dynamicprogramming we usually start with the smallest and hence the simplest sub- instances. by combining their solutions, we obtain the answers to sub-instances of increasing size, until finally we arrive at the solution of the original instances. It follows a bottom-up technique by which it start with smaller and hence simplest sub instances. Combine their solutions to get answer to sub instances of bigger size until we arrive at solution for original instance. Dynamic programming differs from greedy method because greedy method makes only one decision sequence but dynamic programming makes more than one decision.