Dynamic Programming

Bellman, R. (1957). Dynamic Programming. Princeton University Press.

Type

Book

Intellectual base

Review or monograph

Year

1957

Link

https://press.princeton.edu/books/paperback/9780691146683/dynamic-programming

Cited from

computer_science, data_science, information_theory, mathematics, operations_research

Cited by

8 citations across 8 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Backtracking
  • Combining backtracking with memoisation yields a DP-like method, but they are distinct skeletons.

    This sourceIntroduces dynamic programming, which reuses memoized subproblem solutions to avoid recomputation — distinct from plain backtracking.

• Constraint
  • Bellman's 1957 Dynamic Programming
• Curse Of Dimensionality
  • The number of cells in a regular partition of a unit hypercube grows exponentially in the dimension.

    This sourceCoins the "curse of dimensionality": exponential growth in the number of grid cells with dimension, defeating tabular dynamic programming and motivating mitigation.

• Dimension
  • Bellman's 1957 Dynamic Programming

    This sourceIntroduces the principle of optimality and the Bellman equation, and coins 'the curse of dimensionality' for the exponential growth of sample/volume/search cost with dimension.

• Dynamic Programming
  • (2) The distinctive focus is on the recursive decomposition and the systematic reuse of subproblem solutions: where divide-and-conquer decomposes problems into independent subproblems (as in mergesort or quicksort), DP is the technique of choice when subproblems overlap — i.e., when the same subproblem appears many times in the recursive tree, making naive recursion catastrophically wasteful; where branch-and-bound explores a search tree pruning by dual bounds, DP exhaustively builds a table of optimal subproblem solutions and extracts the full problem's optimum by lookup.

    This sourceFoundational monograph: introduces the principle of optimality ("an optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision") and codifies dynamic programming as a unifying framework for sequential decision-making under decomposability.

• Markov Decision Processes (MDPs)
  • Cited in the text; the supporting sentence was not recorded.
• Markov Process
  • Memorylessness collapses an unbounded history into a finite (or at least fixed-shape) present state, replacing the impossible instruction "remember everything that ever happened" with the tractable one "track the current state and apply a transition rule."

Domain-specific

• Reinforcement learning
  • Exploration deliberately chooses actions whose immediate estimated value may be lower because their information can improve future decisions.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:667f2fd1e03b · see in the full table