What is Dynamic programming: Definition and 20 Discussions

Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.
If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems. In the optimization literature this relationship is called the Bellman equation.

View More On Wikipedia.org
Recent contents Top users
  1. C

    Comp Sci Validating Braces Placement for Expression Evaluation

    Here's what I've done: Mentor note: replaced icode tags with code=python and \code pair. def valid_braces_placement(s, L): if len(L)==0: return False string = '' for element in L: string = string + str(element) D = ['+','-','*'] return...
  2. F

    Optimization Problem - Dynamic Programming

    Summary:: Hi, this is an exercise from an algorithm course. I have been trying for hours but I have no successful ideas on how to solve it. I can only understand that DP is the correct approach, since Greedy method does not work. Suppose you have *n* friends that wants to give you an amount of...
  3. C

    DP: proving existence of optimal substructure for "Sherlock and Cost"

    I was attempting to solve the "Sherlock and Cost" problem from HackerRank using DP: But before I went to come up with a recursive relation, I wanted to find if the problem possesses an optimal substructure, and I was following these steps as written at CLRS book: Mentor note: Inline images of...
  4. M

    MHB Dynamic programming: which recurrence relation do we use?

    Hey! :unsure: At the cash register of a store we want to give change of worth $V$ cents of euro. Create and analyze a greedy algorithm that gives the change using the minimum number of coins. Assume that the available coins are the euro subdivisions, i.e. $\{1, 2, 5, 10, 20, 50\}$ and that we...
  5. M

    Dynamic Programming - Restoring white space between words in a file

    All the white space among words in a text file was lost. Write a C++ program which using dynamic programming to get all of the possible original text files (i.e. with white spaces between words) and rank them in order of likelihood with the best possible runtime. You have a text file of...
  6. binbagsss

    Other Operations research, stochastic dynamic programming, sources

    My lecture notes and recommended textbook Hillier and Liberman are not enough for me. My methodology and formulation of problems still seems like too much guess-work. Can anyone recommend any good resources, lecture notes or textbooks, for stochastic DP? Many thanks
  7. S

    Where is my logic wrong in this dynamic programming problem?

    I'm trying to solve https://www.hackerrank.com/challenges/summing-pieces and I think I have come up with an O(n) solution although the numbers aren't coming out exactly right. The problem is essentially to find a sum like ABCD ---> All sets of sets of contiguous subarrays spanning ABCD is {...
  8. Danielm

    Dynamic programming question

    Homework Statement Suppose it’s nearing the end of the semester and you’re taking n courses, each with a final project that still has to be done. Each project will be graded on the following scale: It will be assigned an integer number on a scale of 1 to g > 1, higher numbers being better...
  9. evinda

    MHB Solutions to Transport Problems Using Dynamic Programming

    Hello! (Wave)Suppose that we have $M$ production stations $A_1, \dots, A_M$ of a product and $N$ destination stations $B_1, \dots, B_N$ of the product. We suppose that $x_{ij}$ units of the product are transferred from $A_i$ to $B_j$ where $i=1, \dots, M, j=1, \dots, N$. The cost of...
  10. evinda

    MHB How do we use dynamic programming?

    Hello! (Wave) Could you explain to me how we can use dynamic programming in order to solve a non linear programming problem? What do we do for example if we are given the following problem? $$\max (y_1^3-11 y_1^2+40 y_1+y_2^3-8y_2^2+21 y_2) \\ y_1+y_2 \leq 5.4 \\ y_1, y_2 \geq 0$$
  11. O

    Bellman Equation, Dynamic Programming, state vs control

    Hi, I am proficient in standard dynamic programming techniques. In the standard textbook reference, the state variable and the control variable are separate entities. However, I have seen examples in economics, in which a single variable, let's say consumption, is both a state variable and a...
  12. evinda

    MHB Memoized Dynamic Programming algorithm

    Hello! (Wave) I am looking at the following example of Memoized Dynamic Programming algorithm. memo={} Fib(n): if n in memo return memo[n] if n<=2 F[n]=1 else F[n]=F[n-1]+F[n-2] memo[n]=F[n] return F[n] Could you explain me why we check if $n$ is in memo although memo is a set...
  13. P

    Dynamic Programming with 2 state variables

    Homework Statement Derive the Euler Equation of the dynamic programming problem: \[max_{\{ z_t \}^\infty_{t=0}} \sum_{t=0}^{\infty} \delta^t f(x_t, y_t, z_t) \] subject to: x_{t+1} = g_1(x_t, y_t, z_t), \ y_{t+1} = g_2(x_t, y_t, z_t), \ x_0 = x^0, y_0 = y^0 and where \delta <1...
  14. K

    Dynamic Programming (Approximate, Differential), Model Predictive Control

    Hello, Could someone please explain in a short summary what the difference between the following are: 1. Dynamic Programming from Control Engineering literature and Dynamic programming from Reinforcement learning literature? 2. Approximate Dynamic Programming vs Differential Dynamic...
  15. D

    Dynamic Programming - World Series Probability Example

    Homework Statement Two teams A and B play at most 2n-1 games. For any match there is a constant probability p that A wins and a constant probability q=1-p that B wins. P(i,j) is the probability that A wins; A needs i more wins to win and b needs j more wins to win. At the begin the...
  16. Y

    How to Solve This Dynamic Programming Problem with Two Subsequences?

    I'm having problem to solve this problem in DP: Given 2 subsequences: X = {x1, x2,..., xm} and Y = {y1, y2, ... , yn} so `n <= m` and also `y1 <= y2 <= ... <= yn`. The goal is to find a sub-sequence of `X` (xi1, xi2, ... , xin) such that: sum(k is 1 to n) | xik - yk | is...
  17. Y

    Dynamic Programming: Solving Optimization Problems with Infinite Horizon

    How do we solve optimization problems with infinite horizon. I tried to look online for some guidance but nothing but just problems and no solution methods. For example how can I solve: maximize a_t \in[0,1] \sum\frac{-2a_t}{3}+log(S_T) where sum goes from 0 to T-1 subject to: s_t+1 = s_t...
  18. S

    Dynamic Programming to maximize profit

    Homework Statement Trying to maximize the profit of a farmer using dynamic optimization. Each period the farmer has a stock of seeds. He can plant them at a cost c per seed or sell them for p. Every seed that is planted produces \gamma seeds for next period. In period m there is no longer any...
  19. R

    Sequence Alignment and Dynamic Programming

    Homework Statement I'm having trouble understanding dynamic programming as it relates to sequence alignments. I understand from my lecture notes that the scoring matrix used has arbitrary values (in our case +5 for match, -2 for mismatch, and -6 for gap). I therefore understand why square...
  20. S

    Dynamic Programming Related Questions

    Hi all, (1.) Can someone tell me the difference between a compact valued and single valued correspondence? (2.) I have been seeing repeating themes of "continuity on a compact set". Does that imply boundedness and thus possible to attain maximum? (3.) What's the difference between...
Back
Top