What are the two properties that characterise a good dynamic programming problem?

Answer 1

Dynamic programming is a technique for solving problem and come up an algorithm. Dynamic programming divide the problem into subparts and then solve the subparts and use the solutions of the subparts to come to a solution.The main difference b/w dynamic programming and divide and conquer design technique is that the partial solutions are stored in dynamic programming but are not stored and used in divide and conquer technique.

Answer 2

To address a variety of optimization issues, dynamic programming is a well-liked algorithmic method. It is especially useful for problems that exhibit overlapping subproblems and optimal substructure. There are two main properties that characterize a good dynamic programming problem: optimal substructure and overlapping subproblems.

Overlapping Subproblems:

If an issue can be divided into smaller subproblems that are solved more than once, it has overlapping subproblems. In other words, if we solve the same subproblem multiple times, we are wasting computational resources.

For example, consider the problem of computing the nth Fibonacci number. We can compute the nth Fibonacci number using the formula F(n) = F(n-1) + F(n-2). However, this approach involves recomputing many of the same subproblems multiple times. For instance, when computing F(n-1) and F(n-2), we are recomputing the values of F(n-3), F(n-4), and so on.

Dynamic programming solves this problem by storing the solutions to subproblems in a table or an array. This way, we can avoid recomputing the same subproblems multiple times and instead retrieve their values from the table. This is known as memoization and is a key aspect of dynamic programming.

Optimal Substructure:

A problem exhibits optimal substructure if an optimal solution to the problem can be constructed from optimal solutions to its subproblems. In other words, if we can break down the problem into smaller subproblems, and we know the optimal solution to each subproblem, then we can use these solutions to build the optimal solution to the original problem.

For example, consider the problem of finding the shortest path between two points in a weighted graph. If we know the shortest path between two intermediate points in the graph, we can use this information to determine the shortest path between the original two points. This is so that the shortest path between intermediate locations can be determined, which is a subproblem of the main problem of finding the shortest path between two points.

In summary, a good dynamic programming problem exhibits both optimal substructure and overlapping subproblems. The optimal substructure property allows us to break down the problem into smaller subproblems and construct an optimal solution from optimal solutions to its subproblems. The overlapping subproblems property allows us to avoid recomputing the same subproblems multiple times and instead store their solutions in a table or array. We can create effective algorithms to address a variety of optimization issues by taking advantage of these characteristics.