File size: 2,834 Bytes
8a2dcce | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | TOPIC: Dynamic Programming Overview
DEFINITION: Dynamic programming is a method for solving complex problems by breaking them down into smaller subproblems, solving each subproblem only once, and storing the solutions to subproblems to avoid redundant computation. This approach helps to solve problems that have overlapping subproblems or that can be decomposed into smaller subproblems. It's particularly useful for problems where a naive recursive approach would be inefficient due to the repeated computation of the same subproblems.
TIME_COMPLEXITY: O(n^2) for many dynamic programming problems, where n is the size of the input, although this can vary depending on the specific problem being solved. The key insight is that dynamic programming avoids the exponential time complexity of a naive recursive approach by storing and reusing solutions to subproblems.
SPACE_COMPLEXITY: O(n) for storing the solutions to subproblems in a table, where n is the size of the input. The space is used to store the results of subproblems so that they can be quickly looked up instead of recomputed.
USE_WHEN: Use dynamic programming when a problem can be broken down into smaller subproblems, and the solution to the larger problem depends on the solutions to these subproblems. This approach is particularly useful when the subproblems overlap, meaning that some subproblems may be identical or have similar solutions.
AVOID_WHEN: Avoid using dynamic programming for problems that do not have overlapping subproblems or that cannot be decomposed into smaller subproblems, as the overhead of storing and managing the solutions to subproblems may outweigh any potential benefits. In such cases, a simple recursive or iterative approach may be more suitable.
EXAMPLE:
Consider the problem of finding the minimum number of coins needed to make change for a given amount, using coins of denominations 1, 2, and 5.
Start with amount 0, which requires 0 coins.
For amount 1, the minimum number of coins is 1 (using a coin of denomination 1).
For amount 2, the minimum number of coins is 1 (using a coin of denomination 2).
For amount 3, the minimum number of coins is 2 (using coins of denomination 1 and 2).
...
The final result for amount 6 is:
[0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 5: 1, 6: 1]
Checkmark: The minimum number of coins needed to make change for 6 is 1 (using a coin of denomination 5 and a coin of denomination 1).
REAL_WORLD_ANALOGY: Dynamic programming is like planning a road trip by breaking it down into smaller segments, solving each segment once, and storing the results to avoid getting lost or having to re-route. This approach helps to efficiently find the best route by avoiding redundant calculations.
SOURCE_NOTE: Concepts synthesized from general knowledge of algorithms and data structures. |