Questions tagged [dynamic-programming]
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.
641 questions
0
votes
0
answers
32
views
Determiniing max roundness of number in an array
I'm trying to solve the following Codeforces question (https://codeforces.com/contest/837/problem/D), and I feel like I have a solution that's very close but is probably still over the time constraint....
0
votes
0
answers
27
views
Continuity of an optimal stopping value with discontinuous gain function.
I am trying to approach this homework on optimal stopping. Suppose we have an optimal stopping problem where we observe the process $$dm_t = \frac{1}{1+t}dW_t,$$
where $W_t$ is a standard Brownian ...
- 117
1
vote
0
answers
48
views
Why is "double overshooting" not the optimal strategy in this kind of acceleration problem
https://leetcode.com/problems/race-car/description/
I'm working on a problem where we need to reach a target position t on a number line by accelerating. The acceleration on step k is k.
Let's say we ...
0
votes
3
answers
207
views
How do I find the straightest path through 3D rectangles?
I'm mainly a programmer, not a mathematician, so please bear with me.
I have a sequence of rectangles in 3D space. Each one has a specified pose: position, an orientation (rotation in 3D), and a width ...
- 111
0
votes
0
answers
15
views
Prove concavity for a discrete MDP using Induction
Hi I am new to MDP and need to do a modeling for my project. I am really not comfortable with the entire abstraction of optimizing actions so I really need some help!! Thank you all in advance!!!
The ...
- 1
3
votes
1
answer
155
views
Counting the number of non-bypassing yet possibly intersecting path pairs on a grid
Consider an integer lattice path beginning at the origin with each step going rightwards or upwards. That is, a valid path starts at $(0,0)$, ends at $(m,n)$, and each step is a vector of the form $R=(...
- 687
0
votes
0
answers
32
views
Uniqueness of interior fixed point in a dynamic programming problem with strictly concave objective
Consider the following dynamic programming problem:
$$
V(s)=\max_{s'\in[0,1]}F\left(s,s'\right)+\beta V(s').
$$
Here $\beta\in[0,1)$ is the discount rate, $s\in\mathbb{R}$, and
$F:\mathbb{R}^{2}\...
- 95
-1
votes
1
answer
141
views
Is there any easy way to calculate total number of combination of a permutation of n such that all adjacent element's sum is composite?
A permutation of length $n$ is a sequence where every number from $1$ to $n$ comes exactly $1$ times, so permutation of $5 \mapsto 1,2,3,4,5$ but $1,1,2,3,5$ is not a permutation of $5$.
Now we try to ...
- 11
0
votes
0
answers
114
views
Dynamic Programming
I am struggling with the following problem.
A college student has 7 days remaining before final examinations begin in her four courses, and she wants to allocate this study time as effectively as ...
- 1
0
votes
0
answers
53
views
Optimal stopping time in discrete time, deterministic setup
I want to solve a very simple optimal stopping time problem. Let us assume that an agent derives some "utility" in each period t, equal to $u_{t}$. This is assumed to decay geometrically: $...
- 115
1
vote
1
answer
112
views
How to prove optimal substructure in dynamic programming?
There are 2 requirements for a problem to be considered for dynamic programming:
overlapping sub-problems
optimal sub-structure
Majority of dp problems are modeled as recursive functions where the ...
- 11
0
votes
1
answer
60
views
Prove that $π^*(s | a) = δ(a, \arg\max_{a\in A} Q(s, a))$ is an optimal policy.
In a Markov Decision Process, a policy is a probability distribution over which actions to take given states:
$$\pi(a \mid s) = \mathbb{P}(A_t = a \mid S_t = s)$$
The state-value of a state $s_t$ when ...
2
votes
0
answers
113
views
Maximize expected stopping time of a random walk with absorbing barriers
Consider a discrete-time random process $\{X_t\}$ $(t = 0, 1, 2, \cdots)$ on the lattice $\mathbb{Z}^M$. Starting from the point $X_0 = (X^1_0, \cdots, X^M_0)$ satisfying
$$
X^1_0 + \cdots + X^M_0 = N ...
- 717
4
votes
0
answers
140
views
Guessing a subset by submitting subsets and getting back the sizes of the intersections
Let $p>q$ be positive integers, set $P=\{1,2,...,p\}$, and $Q\subset P$ be an unknown set of $q$ elements.
In every step, we can guess a set $T\subset P$ and then know the size $|T\cap Q|$ of its ...
- 41
0
votes
0
answers
53
views
Optimizing code to find optimal value of integer polynomial
I'm writing a Python program to calculate the maximum value of a polynomial $p * (1 + (d * (1 + (o * (1 + g))))$, subject to the constraints that $p$, $d$, $o$ and $g$ are all positive integers, and $...
- 1
0
votes
0
answers
37
views
FORMAL derivation of HJB equation in deterministic case (continuous-time setting)
Is there a formal derivation for HJB equation in deterministic and continuous-time setting? I already knew the formal derivation of stochastic and continous-time case from Pham (2009). I checked ...
- 39
0
votes
0
answers
99
views
Expected value of operation on 2 number array
I was inspired by this question, and thought of the following similar question. Consider an array of 2 positive integers $(x, y)$. An improvement operations has a $\dfrac{x}{x+y}$ chance of increasing ...
0
votes
0
answers
942
views
Count the Minimum Operations of making an array's all subarrays' sum non-negative.
I have encountered an question in interview. Given an array arr of n integers, make the array positive with the following operation: In one operation, select integers i (0 ≤ i < n) and x (-10^18 ≤ ...
1
vote
1
answer
119
views
Subset Sum variation where $x_i \in \{-1,1\}$ instead of $x_i \in \{0,1\}$
Consider the subset sum problem: for $n,m \in \mathbb{N}$ let $S \in \mathbb{N}^n$ with $s_i \leq 2^m$. The Subset Sum Problem asks for a given $T_S \in \mathbb{N}$ whether exists $x \in \{0,1\}^n$ ...
- 1,505
4
votes
1
answer
276
views
Optimal game order for God Gamer challenge?
The challenge (if I'm not mistaken) is to play 10 different multiplayer games and win in all of them back to back. If you ever lose any of them, you need to start from the beginning. The question is: ...
- 2,506
7
votes
2
answers
321
views
Probability of encountering $5$ consecutive equal rolls in $100$ dice rolls?
This question is a creative thought of mine that I stumbled upon while studying some basic probability and statistics:
Problem
What is the probability of encountering $5$ consecutive equal rolls in $...
- 101
5
votes
0
answers
105
views
Analytical Solution for a 2D Recurrence Relation
How can I analytically solve the following 2D recurrence relation?
$$
f(n,m) = \frac{n}{n+m}f(n-1, m+1) + \frac{m}{n+m}f(n, m-1) + 1
$$
with the boundary conditions:
$$
f(0,m) = 0
$$
$$
f(n, 0) = f(n-...
- 1,393
1
vote
0
answers
54
views
Optimal strategy for a free throw game
My friend recently showed me a game designed to help drill free throws in basketball. I'm interested in calculating an optimal strategy but I've gotten stuck.
Rules of the game
Players, taking turns ...
- 11
1
vote
1
answer
70
views
Deriving equation for a Dynamic programming Puzzle [closed]
I solved the following puzzle https://leetcode.com/problems/unique-paths/description/ here at leetcode using programming. It is not very difficult to reason about how to computationally get the answer....
1
vote
0
answers
111
views
Generalization of 1D DP frog jump problem
A frog is travelling from point A $(0,0)$ to point B $(5,6)$ but each step can only be $1$ or $2$ units up or right. Compute the number of ways the frog can move from A to B.
I have solved a question ...
- 9,526
10
votes
5
answers
8k
views
Compute the number of ways the frog can move from A to B.
A frog is travelling from point A $(0,0)$ to point B $(5,6)$ but each step can only be $1$ unit up or $1$ unit to the right. Also, the frog refuses to move three steps in the same direction ...
- 9,526
0
votes
1
answer
80
views
Dynamic programming, optimization problem where decision leads to multiple overlapping subproblem. [closed]
In the matrix chain multiplication (MCM) problem each time we apply a decision of parentizing an expresion $e=(e_1)(e_2)$ we have two subproblems to solve but they are not overlapping. Indeed, solving ...
- 1,813
3
votes
1
answer
109
views
Relationship of the Egg Riddle solution to bisection and $\log(N)$ function?
I stumbled upon the video "Can you solve the egg drop riddle? - Yossi Elran" on the TED-Ed YouTube channel.
What I found interesting is that in the solution, given that the triangle numbers ...
- 31
1
vote
0
answers
21
views
Matrix parenthesization problem expressed as Markov decision problem
I am trying to understand the relation between dynamic programming an Markov decision processes because I noticed many dynamic programming problems can be expressed in a MDP. In particular, I am ...
- 1,813
2
votes
1
answer
201
views
Arrange given numbers in a way such that the minimum absolute difference between any two consecutive numbers is maximized.
I've been doing some competitive programming practice on Codeforces recently, and I stumbled upon a problem here. The solution to this problem can be found here.
Now, what if the set of numbers wasn't ...
- 21
0
votes
1
answer
93
views
Minimum Cell Changes to Ensure Unique Numbers in Each Row and Column of an $ n \times n $ Table
We have an $ n \times n $ table, and in each cell of the table, there is a number from $1$ to $ 2n $. We want to change the numbers in some of the cells and replace them with other numbers from $1$ to ...
- 145
0
votes
0
answers
37
views
Reading material for Bellman's optimality principle in dynamic programming - for someone who is not familiar with control theory
I am trying to understand the underlying theory behind dynamic programming, given the fact that I am not familiar with control theory, I fail to find relevant reading material that addresses the this ...
0
votes
1
answer
84
views
Maximum function recursive property
In an old book by Richard Bellman, I found a proof of the initial Bellman equation:
$$
f_n(x)=\max_{0\le x_N\le x}\left[g_N(x_N)+f_{N-1}(x-x_N)\right]
$$
where $x_i\ge 0$ and $\sum_{i=1}^Nx_i=x$. ...
- 499
1
vote
0
answers
55
views
Knapsack with fixed number of bins?
Constant: d, a fixed number of bins/sacks
Input:
$v_1,v_2,...,v_n$ item profits,
$0<w_1,w_2,...,w_n\leq1$ item weights.
Output: $B_1,B_2,...,B_d$ which are d subsets of $\{1,2,...,n\}$ s.t. they ...
- 11
0
votes
1
answer
85
views
Definition of the value function in control theory
The following definition stems from the notes "An Introduction to Mathematical Optimal Control Theory" by Lawrence C. Evans (they are available online for free).
In defining the value ...
0
votes
1
answer
61
views
simultaneous subset sum problem and pseudo polynomial algorithm
Given $S \in \mathbb{N}^{q\times n}$ for $q < n $ natural numbers, is there a pseudo-polynomial algorithm which can decide whether exists $x \in \{0,1\}^n$ such that
$$
S \cdot x = \begin{bmatrix}...
- 1,505
3
votes
1
answer
204
views
How to solve a given combinatorial problem?
Given $n$ balls, which are numbered from $1$ to $n$, and also $n$ boxes, which are also numbered from $1$ to $n$. Initially, $i$-th ball is placed at $i$-th box. Then we are doing the following ...
- 33
2
votes
0
answers
86
views
Is it true that if the path $a \to b \to c$ is optimal, then the path $a \to b$ is optimal?
Suppose that the path $a \to b \to c$ from vertex $a$ to vertex $c$ on a directed acyclic graph is optimal. Then, is the path $a \to b$ necessarily the optimal path from vertex $a$ to vertex $b$? I ...
- 1,538
1
vote
0
answers
154
views
Mathematical and Intuitive understanding of "Optimal Substructure"
Wikipedia formally puts the definition of optimal substructure as below:
"A slightly more formal definition of optimal substructure can be given. Let a "problem" be a collection of &...
0
votes
0
answers
69
views
Indexability of Restless Multi-Armed Bandit Problem
While reading a book on Restless multi-armed bandit problem (specifically Ch.6 of J.C. Gittins, 2011: Multi‐Armed Bandit Allocation Indices), the idea of indexability comes up yet I find it hard to ...
- 39
1
vote
0
answers
77
views
Understanding the Relationship Between Bellman Equation and Optimal Stopping Conditions in Sequential Decision Making
I'm interested in exploring the connection between the Bellman equation, commonly used in dynamic programming, and the backward induction equation associated with optimal stopping conditions, ...
- 211
2
votes
0
answers
51
views
Dynamic Programming with Finite Horizon, Different Ranges of Parameters
A dynamic programming exercise in homework.
Consider the following problem, where $R$ and $b$ are given, and solve for $ \{
c_t,A_{t+1} \} _{t=0}^T $. $$ \max_{\{c_t,A_{t+1}\}_{t=0}^T} \sum_{t=0}^T \...
- 53
2
votes
1
answer
79
views
The minimum time to evaluate an arithmetic expression.
I have an arithmetic expression and I want to find the minimum time to compute this expression knowing the delay of each operator. The operators are addition, subtraction, multiplication, and ...
- 61
2
votes
3
answers
183
views
Probability of crossing value $N= 1000$ with face $k$ when adding up 6-sided dice rolls? Also two 6-sided dice?
We roll a 6-side die repeatedly until the accumulated sum exceeds $N=1000$. What is the probability that the last roll (last face) equals $k$?
I've tried doing this by hand: We go over 1000 with 1 by ...
- 347
1
vote
0
answers
123
views
Monte Carlo Control Reinforcement Learning
I'm reading the "Reinforcement Learning" book by Sutton & Barto. It's available here http://incompleteideas.net/book/RLbook2020.pdf . I'm currently in chapter 5 on Monte Carlo methods.
I ...
- 31
-1
votes
2
answers
72
views
Identify optimal product size configuration based on historical data and some constraints [closed]
We have historical data for the demand of a product. Product can be demanded in any quantity between 0-1000g and the historical data show the distribution of previous request sizes. We can only pack ...
2
votes
0
answers
133
views
Hamilton Jacobi Bellman and uniqueness
In the framework of optimal control we have introduced in class the HJB equation to solve optimal control problem of the form
$$
\inf_{u\in\mathcal{U}}\left[\int_{0}^{T}L(t,x_u(t),u(t))dt + h(x_u(T));\...
- 1,657
3
votes
0
answers
131
views
Dynamic programming, prove function is monotone non-decreasing
I am currently studying dynamic programming using the Bersketas book: Dynamic programming and optimal control, volume 1. The question is regarding the notation used, but is the following:
Example 7.3....
- 153
1
vote
1
answer
155
views
Proof Needed: Minimum # of coins needed to make a given sum
We have infinite supply of these 5 coins:
$1, 3, 6, 10, 15$
Find the minimum number of these coins required such that their total value sums up to exactly $n$.
Example:
For $n = 425$, answer is $29$.
...
- 125
1
vote
0
answers
66
views
Stability of the viscosity solution for the HJB - stochastic optimal control
I am following chapter 4 of this paper (1).
Background information: The stochastic differential equations (eq’s 4.2 to 4.5) are given by:
$$
\begin{aligned}
& d S_t=\sqrt{\nu_t} d W_t \\
& d \...
