dynamic programming

Question 1

Dynamic programming(shortcut)

What is optimal solution

Answer 1

Used to solve optimization problems(To find optimal solutions)

in optimal solution, we either find maximum value or minimum value

Question 2

Definition of dyn prog

its features

Answer 2

Technology that breaks problem into sub problems and saves the result for the future purposes so that we don’t need to compute it again and again
Overlapping sub problems
Features:
1. Optimal substructure property
2.overlapping subproblems

Question 3

Explanation of features of dyn prog

Answer 3

1. Optimal substructure property: problem is divided or divisible into sub trees And solved like divide and conquer
2. Overlapping sub problems: sub problems will be repeated so solved sub problem can be stored and whenever required again can be used(Not like dividend conquer).

Question 4

Knapsack problem

Answer 4

Suppose we have a knapsack or a bag with a limited capacity and each item has some weight and value
prob Which item should be placed in the back so that weight does not exceed and total value of items is maximum( as much as possible)
eg Suppose there is a thief and hunters in museum he contains a knapsack of limited weight capacity. the museum Contains various items of different values. The thief must decide what he should keep in the bag so that profit would be maximum