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.
640 questions
0
votes
0
answers
23
views
Max–min assignment on a DAG when nodes have candidate values with compatibility constraints
I have a DAG where every node has a (usually small) set of candidate integers. A candidate a is compatible with b if (a | b) or (b | a). For every root I want to choose one candidate per node to ...
- 81
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
29
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
51
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
212
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
16
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
142
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
116
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
54
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
114
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
141
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