Dynamic programming is a mathematical optimization/programming approach applicable if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. A classic example is the Towers of Hanoi.
Questions tagged [dynamic-programming]
609 questions
1
vote
0 answers
Dynamic programming and empirical estimation
Consider a finite time horizon $T$. Let there be $N$ Bernoulli distributions with unknown means $\nu_n=\text{Bern}(\mu_n)$ (although we can assume a prior if necessary). In each iteration $t$, we draw samples from the distributions through choice of…
Erik M
- 2,391
1
vote
0 answers
Explanation of "Guess and Verify" Analytical Solution To Bellman Equation
According to my textbook, the analytical technique for solving a Bellman's Equation is as follows:
Guess a form for $V_0(x)$
Solve the maximization problem with respect to the control and obtain a policy function x′=h0(x)
Update the guess by…
1
vote
0 answers
Problem in understanding how to apply Dynamic Programming applied to a Stock Option
I am trying to follow an example in which dynamic programming (DP) is applied to a stock option. I'm familiar with option theory but I'm new to DP.
$F_s(x)$ is the value of the american call option with s days to go, x is the stock price, p is the…
Bazman
- 899
1
vote
0 answers
Exam question from dynamic programming
I've got the following problem from an exam which shall be solved using dynamic programming and wanted to ask if the following is a valid solution: (I uploaded the tables 1-6 here: http://ibb.co/nG3YBR )
Problem:
Little Nick gets two dollars from…
Vincent
- 11
1
vote
2 answers
How many ways to make i integers of set S sum to k
I am looking for an algorithmic approach to solving this general problem, where I have a set of integers, $S=\{0,1,2,3,4,5\}$ and I want to find the number of combinations of $i$ (say 7) integers from set $S$ that sum to $k$ (say 17). I am led to…
user3725021
- 113
1
vote
0 answers
Minimum number of Coins needed to make change?
I was trying to solve the one particular problem and I ended up reading this. I read this question
Above link states the problem of changing the amount when coins are given in infinite amount. Solution for this problem requires DP with little bit of…
hemal7735
- 173
1
vote
1 answer
Knapsack for table
I have a problem that I can't solve. There is this
table.
I have to optimaly allocate 1 million dollars among the five products. I think it looks like knapsack problem but I am not sure. If I want to solve this for what should I look? If it is…
R. Vait
- 111
1
vote
0 answers
All combinations of matrix parenthesizations
I have this problem:
Let $S$ be a set which is the domain with two operators $+$ and $*$
and an element $0$ such that:
$+$ is a binary operator that is:
associative
commutative
idempotent (that is, $x + x = x$ for all $x \in S$)
$x + 0 = 0 + x =…
someone 123
- 11
- 1
1
vote
0 answers
Optimal Stopping Problem (With looking backwards)
Say you are trying to sell a good at the highest price. You draw independently from $F(p)$. The history of observations is $P = \{p_1, p_2,\dots\}$. Observing the $i$th price costs $c_i$, where the observation cost weakly increases with every…
FooBar
- 1,059
- 6
- 15
0
votes
1 answer
Shortest path problem-minimal cost
Given a set of m things (1,2,...,m), we want to group them in clusters that contain adjacent things. For each cluster there is a cost $c_{ij}$. We are looking for the grouping in clusters so that the total cost is minimal. I am asked to write this…
Mary Star
- 13,956
0
votes
0 answers
Longest Common Subsequence (LCS) - Why is the padded string Z_{x_m} a common subsequence of X and Y in the LCS problem?
I am currently studying the Longest Common Subsequence problem. Here is how the problem is defined in the notes I am reading:
Let $X=x_1...x_m$ and $Y=y_1...y_n$ be strings. Let $Z=z_1...z_k$ denote their LCS.
The notes then state:
If $Z$ does not…
0
votes
0 answers
The sum of difference in all pairs in an array
I have an array of 2n distinct non-negative integers, the goal is to find if it's possible to put all integers into pairs such that the sum of the absolute difference of all pairs is equal to a specific number x.
Example: [1, 2, 3, 5, 8, 10]
If x=5,…
att9899
- 1
0
votes
0 answers
How can i Maximize the total number of contacts
Suppose we have 2d array A (n by n) and string S. Each cell of array can contain at most one char. Each character of the string can assign only one cell. The two consecutive characters on the string must be positioned to the neighboring cell of the…
0
votes
0 answers
Optimal Binary Search Tree
Construct an optimal binary search tree for 4 keys with $p_1 = 0.1$, $p_2 = 0.4$, $p_3 = 0.2$, $p_4 = 0.3$ using dynamic programming. Show the tables as well.
What really confuses me is how keys are ordered in this example? I have encountered with…
rasul_rza24
- 81
0
votes
1 answer
Dynamic programming: find possible sums of given digits to reach given sum
Maybe anyone has idea how to solve this problem using dynamic programming: I have a natural number. Let’s name it n. Then, have digits: 1, 3, 4. I have to find all possible sums (with repetitives) of n using digits above. For example.
n=3. Then…
