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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
20 views

How To Prove Recurrences Via Inequalities

To demonstrate my problem, consider the following recurrence for the set cover problem please: $T[X,j] = \text{min}(T[X,j-1], 1+T[X \setminus F_{j},j-1])$, where $T[X,j]$ is the minimum size of a set $...
Yavuz Bozkurt's user avatar
-3 votes
0 answers
36 views

Help with interesting DP problem! [closed]

You have a matrix $M$ of size $n$ by $n$, filled with both positive and negative numbers. The objective is to find a path from the top-left corner to the bottom-right corner of this matrix that ...
reb1rth's user avatar
  • 11
-1 votes
0 answers
44 views

calculating the probability of winning a streak, what approach should I take? [closed]

Here is the game: $A$ plays against $B$. Each round, $A$ has probability $a$ of winning, $B$ has a probability $b$ of winning, and the probability of a draw is $d$. So $a+b+d=1$. Each round is ...
user1289663's user avatar
0 votes
0 answers
24 views

How to show the existence of a Bellman Equation Solution?

consider the Bellman Equation \begin{equation*} V(\alpha)=\max_{\beta} f(\beta,\alpha)+A(\beta,\alpha) V(\alpha)+B(\beta,\alpha) V'(\alpha) \end{equation*} How can I show the existence of the solution?...
Isn't Adobe Acrobat the best's user avatar
0 votes
0 answers
25 views

Optimal Piecewise Linear Upper Bound for a function

I am looking for the optimal piecewise linear upper bound for a single variable function $f(x)$ - specified as a list of $(x,f(x))$ pairs. So, I have $(x_1,f(x_1)),(x_2,f(x_2)), \ldots, (x_n,f(x_n))$. ...
dexter04's user avatar
  • 1,971
0 votes
1 answer
33 views

Expected number of target points visited by a path from origin to destination

There is a robot on a 0-indexed $m \times n$ grid. The robot is initially located at the top-left corner (i.e., origin, grid[0][0]). The robot tries to move to the bottom-right corner (i.e., ...
Francis's user avatar
  • 121
0 votes
2 answers
44 views

Intertemporal optimization: When to use the Hamiltonian vs Lagrangian

Assume a producer wishes to maximize the net present value, choosing optimal quantities of K and L. variables are time dependent. y is the production, p is the price of y. K is capital, r is the price ...
Meg's user avatar
  • 15
0 votes
0 answers
19 views

What is a Viterbi algorithm that exploits sparseness of transition matrix?

What is a Viterbi algorithm that exploits sparseness of transition matrix? In PYIN: A FUNDAMENTAL FREQUENCY ESTIMATOR USING PROBABILISTIC THRESHOLD DISTRIBUTIONS Matthias Mauch and Simon Dixon https://...
mavavilj's user avatar
  • 7,222
0 votes
0 answers
12 views

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 ...
southland's user avatar
-1 votes
1 answer
48 views

Expected value of max((y-w),0) [closed]

Trying to solve a dynamic programming inventory control problem for a final research paper for a graduate dynamic programming (CS/Industrial Systems Eng.) course, which involves an expectation E(max(y-...
patrick_91234's user avatar
1 vote
1 answer
43 views

Hardness of a Hybrid problem combining knapsack and scheduling

I am trying to prove whether the following problem is NP-hard or not: Items with a certain length arrive in a fixed sequence and must be assigned to one of two containers which are constrained in ...
Christian's user avatar
0 votes
0 answers
20 views

Help me understand the application on Bayes' Theorem in this case

I am studying a paper (https://www.jstor.org/stable/1804124) which discusses a two period revenue optimization problem as follows We are trying the sell a single unit of product over two periods, i.e. ...
Ricky Doo's user avatar
0 votes
0 answers
48 views

Necessary optimality conditions: $\min_{\phi} \sum_\xi\int_{0}^{1} p(a,\xi) T(V_{w(a,\xi)}[\phi]) da$, where $V[\cdot]$ is an evaluation functional

I'm trying to set up a dynamic optimization problem as follows. Let $\mathcal{W} := [\underline{w},\overline{w}]$, and $w:[0,1]\times\{0,\dots,N\}\to \mathcal{W}$ \begin{align} \min_{\phi: \mathcal{W}\...
Uomond's user avatar
  • 21
1 vote
0 answers
66 views

Does there exist a connection between the Markov Chains and Dynamic Programming?

For context, I currently taking a class on Probability Modeling and I also happen to be teaching Dynamic Programming (Graduate Seminar), in the former class the instructor is starting to teach us ...
Miss Mae's user avatar
  • 1,028
0 votes
0 answers
42 views

Dynamic Programming: Single-Agent Problem

My question is about equations (1) and (2) in Butters, Dorsey, and Gowrisankaran (2023). This is an economics paper in energy / battery storage. My question is about how to get from equation (1) to ...
SarahZ233's user avatar
0 votes
0 answers
22 views

Struggling to Derive First-Order Condition in Lucas (2004) on Optimal Control

I am reading Robert Lucas (2004), Life Earnings and Rural-Urban Migration, and I came across a rather peculiar optimal control problem that I'd like to ask about. Thank you! The objective function is $...
zz Matthew's user avatar
3 votes
2 answers
307 views

Number of sequences that satisfy the absolute difference condition

Let $x_0 =0$ and let $x_1,.....x_{10}$ satisfy that $|x_i - x_{i-1}|$ = 1 for 1≤i≤10 and $x_{10} = 4$ . How many such sequences are there satisfying these conditions? I tried to calculate it by ...
Kinshuk's user avatar
  • 31
0 votes
1 answer
126 views

Is there a closed form for the Josephus Problem on a line?

Consider the following variation of the famous Josephus problem: The numbers 1 through $n$ are lined up. Each round, every $k$th number is eliminated, starting from the first one (so the numbers in ...
Random Person's user avatar
1 vote
0 answers
37 views

differential dynamic programming : Intuition, key idea and difference from dynamic programming

I cam across 'Differential Dynamic Programming' in a course on Optimal Control. In this course , we were introduced to Dynamic Programming prior to DDP. I went through the Wikipedia Post on ...
Amor Rei's user avatar
1 vote
1 answer
49 views

Proof that the least number of steps to some value $i$ if you can only travel in increasing powers of 2, is never done by overshooting $2i$

The problem: This question is inspired by a proof of correctness for the algorithms question that can be found here To summarize, starting from $0$, you want to get to some target $i > 0$. You may ...
punypaw's user avatar
  • 455
-2 votes
1 answer
61 views

Contest problem(Combinatorics//maybe DP)

Problem : There are n people in a party. Each person can either join dance as a single individual or as a pair with any other. Find the number of different ways in which all n people can join the ...
Isam's user avatar
  • 67
0 votes
1 answer
110 views

Knapsack problem with overload

Let $N = \{1, 2, \ldots, n\}$ denote a set of items, $w \in \mathbb{R}_{++}^N$ a vector of weights, $c > 0$ a constant and $x \in \{0, 1\}^N$ a decision variable. The objective is to minimally ...
clueless's user avatar
  • 771
2 votes
1 answer
95 views

Find the number of subsets of n chairs in a circle containing at least three adjacent chairs

Find the number of subsets of $n$ chairs in a circle containing at least three adjacent chairs. I know that the answer for $n=10$ is $581$, and the solution is here for instance. I'm not sure if it's ...
user1127's user avatar
  • 293
0 votes
1 answer
50 views

What is the probability that no 2 adjacent bits are 1?

Given a binary vector, what is the probability that no 2 adjacent bits are 1? Let's say the probability for value 1 is p. I ...
MathQues's user avatar
1 vote
0 answers
59 views

Optimality of greedy knapsack algorithm.

Consider the array of tuples $(t_i, p_i, q_i)$, where $t_i \in \{0, 1\}$ means type of order ($0$ for sell and $1$ for buy), $p_i$ is price of order and $q_i \in (0, 1)$ is volume of the order. Assume ...
openspace's user avatar
  • 6,458
0 votes
1 answer
93 views

ILP constraints for connectivity in a matrix

I'm trying to use ILP to solve the following problem: A series of connected nodes are provided. For the example below, $a$ is only connected to $b$, $b$ is connected to both $a$ and $c$, $c$ is ...
Amanli's user avatar
  • 11
4 votes
0 answers
91 views

Consequence of Dvoretzky Stochastic Approximation Theorem

I am having some problems trying to apply Dvoretzky Stochastic Approximation Theorem to one Lemma used in a paper I found about the proof of convergence of some reinforcement learning temporal ...
Kareit's user avatar
  • 41
0 votes
1 answer
114 views

Why are the costate equations solved backwards in time?

I'm trying to find an optimal control to a simple nonlinear SIR model. I am trying to undersand the Pontryagin minimum principle but I don't understand why the costate equations must be solved ...
CHOSM's user avatar
  • 148
1 vote
0 answers
41 views

optimal indicator function on a grid

Consider the grid $X =\{ 0,1,\ldots,m-1\}\times \{ 0,1,\ldots,n-1\}$ of size $m \times n$. An indicator function $f:X\mapsto \{ 0,1\}$ on this grid is defined to be monotonic, if $ i\leq s, j \leq t \...
ChargeShivers's user avatar
3 votes
2 answers
601 views

Count the ways to divide 18 colored and numbered balls into 6 groups

Consider a box has $18$ balls, $6$ white balls numbered $1$ to $6$, $6$ black balls numbered $1$ to $6$ and $6$ red balls numbered $1$ to $6$. We have to divide all $18$ balls into $6$ groups (groups ...
Chesx's user avatar
  • 469
0 votes
0 answers
23 views

Does there exist an MDP policy with this property?

Consider a discrete-time MDP with finite states and actions. For any policy $\pi$ and state $s$, let $u_t^{\pi}(s)$ be the expected total reward for using $\pi$ at times $t, t+1, ..., N$ if the ...
AMfrn's user avatar
  • 11
0 votes
1 answer
266 views

Proving a function satisfying Bellman's equation is optimal

The Question I'd like to prove that a function $V$ (like in reinforcement learning) is optimal iff it satisfies the Bellman equation. A lot of places online reference this fact, but none prove it. ...
snatchysquid's user avatar
6 votes
5 answers
455 views

Math competition question about ways to spell BANANA in a square

This is a math competition question I did. Essentially, starting at B, a move consists of moving to a non-diagonal adjacent square and noting the letter you land on (with the exception of the starting ...
d0uble_a_b4ttery's user avatar
0 votes
0 answers
37 views

What if the reward of an action in MDP(Markov Decision Process) is not immediately known.

We know that in MDP the reward of an action is required to be immediately known. What if the reward of an action in MDP(Markov Decision Process) is dependent on the later state. For example, consider ...
koko's user avatar
  • 49
0 votes
0 answers
91 views

Optimal Control: Can I express a Macroeconomic model as a state space control system?

Both Recursive Macroeconomic models and Control theory problems use ideas from the calculus of variations to estimate unknown functions. In the case of a Macroeconomic model--as shown below--that ...
krishnab's user avatar
  • 2,341
1 vote
1 answer
229 views

Solution to Primer Coin Flip Game

I wonder how to find the optimal action for every possible situation in Primer's Coin Flip game. There is an interactive version as well. A coin has a $0.5$ probability of being a cheater coin and if ...
NinoDS's user avatar
  • 11
1 vote
1 answer
51 views

Dynamic optimisation calculus

Reading a paper on stochastic dynamic optimisation, I got stuck on a (seemingly) simple algebraic step. The starting equation is as follows: $$\rho (\alpha+\theta N^{1-\eta})=\frac{1}{1-\eta}\left((\...
Alessandro's user avatar
0 votes
1 answer
40 views

Unable to understand the base cases for this recurrence relation: DPn = DPn-1 + DPn-3 + DPn-4

I read the following here Sub-problem: DPn be the number of ways to write N as the sum of 1, 3, and 4. Finding recurrence: Consider one possible solution, n = x1 + x2 + ... xn. If the last number is 1,...
Mathovermyhead's user avatar
0 votes
0 answers
39 views

Search Algorithm: Combination of two numbers (Proof)

In several applications or examples in Computer Science (Algorithms & Data Structures), one needs to find two numbers $a_S$, $b_S$ out of two different ordered sequences $A$ and $B$ which summed ...
Michel H's user avatar
  • 252
0 votes
0 answers
22 views

Special Case - How to generate a formula to calculate where next additional items in a set of items, in a particular row and at a particular index

I've tried to generate a simple formula to do this calculation but I've not successfully arrived at a working formula. Here, I have a list of items displayed in a grid. Let's use these symbols ...
Henry Obiaraije's user avatar
4 votes
0 answers
80 views

Calculate probability of flipping coins with probabilities dependent on previous results

Let's say I have a biased coin that has a probability of 0.2 for heads and 0.8 for tails. If you flip it 6 times without getting a heads however, the probability of heads increases by 0.2 per non-...
SillySlimeSimon's user avatar
1 vote
0 answers
72 views

Dynamic programming algorithm to maximize job execution steps on two machines

I have a problem that requires finding a plan to execute a job on two machines, A and B, or moving the job between machines to maximize the number of executed steps. Specifically, in each time ...
umm2996's user avatar
  • 11
1 vote
0 answers
44 views

How can I prove the contraction property on a joint system of equations?

I'm studying a simple dynamic programming problem whose solution is a system of Bellman equations, and am running into some issues trying to prove the Contraction Mapping Theorem for the system as a ...
C_A_Pepe's user avatar
0 votes
2 answers
139 views

repeatedly XOR n-bit string - probability of getting all 1s

Start with n-bits of all 0s Each round, generate a n-bit string, delta, with probability of getting a 1 being p. Output of the ...
Maximus1987's user avatar
1 vote
2 answers
63 views

A Basic Question of Continuous Time Macroeconomic Model (Variation of Constant to Solve an ODE)

I am going through the continuous time macro slides by Ben Moll (link is: https://benjaminmoll.com/wp-content/uploads/2019/07/Lecture2_ECO521.pdf), when deriving New keynesian model in continuous time,...
QLin's user avatar
  • 21
2 votes
1 answer
53 views

Optimal Edition from string $X$ to string $Y$

$\newcommand{\restrict}[2]{{#1}\restriction_{#2}}$ $\newcommand{\cardinal}[1]{\abs{#1}}$ $\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}$ $\newcommand{\append}[2]{\operatorname{ap}\left(#1,#2\right)...
Ziqi Fan's user avatar
  • 1,816
1 vote
1 answer
243 views

Is there always an optimal deterministic policy in MDPs with a continuous state space?

It is well known that in MDPs with a discrete state space, there exists a deterministic policy that is optimal, in the sense that it maximizes the total expected discounted reward from any initial ...
user675763's user avatar
0 votes
0 answers
75 views

Solving a Stochastic Dynamic Programming with Vector State

Consider the following stochastic dynamic program (SDP): $$ V_t(\textbf{s}_t)= \max_{\textbf{a}_t\in A_t(x_t)} \{(1-\lambda(a_t))V_{t+1}(\textbf{s}_t) + \lambda(a_t)(r_t(a_t)+V_{t+1}(\textbf{s}_t-\...
EagleEdge0423's user avatar
0 votes
0 answers
40 views

Solving a functional equation with dynamic programming (Preparation for mathematics competition)

This question is based a bit on an "Ansatz" but I hope my intuition is right. I was practising functional equations for a mathematics competition and I encountered the following equation: $f(...
David's user avatar
  • 15
-2 votes
1 answer
90 views

Interviews of students with professors [closed]

A professor interviews n students, and each student enters the interview in turn. The student only needs to answer how many people can pass the interview. The professor can freely decide whether the ...
Xu Shan's user avatar
  • 106

1
2 3 4 5
13