Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
1answer
60 views

dynamic programming - recursion

We have $n$ requests to plant trees. Each request comes with a position $p_i$ which means we have to plant the tree $p_i$ meters away from a specific constant point. Also, there should not be another ...
0
votes
1answer
330 views

Dynamic Programming: Largest Number of Dams that can be built

Because of the recent droughts, $N$ proposals have been made to dam the Murray river. The $i$-th proposal asks to place a dam $x_i$ meters from the head of the river (i.e., from the source of the ...
1
vote
0answers
31 views

Number of different ways in which you can have 'c' parts (not necessarily rectangular) of a rectangular board

You are given a rectangular board of $A$ rows where each row contains $B$ square shaped boxes. Each square box has a unique integer written on it in the row major order (starting from $1$ to $A\cdot B$...
0
votes
1answer
41 views

Assign sequence based on simple calculation

I'm developing a model for truck sequencing at a warehouse. I want to sequence the trucks based on a value ($Q$) equal to the multiplication of their priority ($\alpha$), arrival time (continuous ...
0
votes
0answers
26 views

Partition problem where partition are in increasing order.

For given $n$ and $S$, how many possible combinations are there such that: $x_1 + x_2 + .. + x_n = S $ $\forall i, x_i \leq x_{i+1}$ $\&$ $x_i \geq 1$ For example, if $n$ = 3 and $S$ = 5, there ...
0
votes
1answer
63 views

Dynamic Programming Winning Strategy

Describing A Game: In the Game there are 2 players (player 1 and player 2) and there is a board with a number of ball in it $n$.There is also a set $A =${$A1...Am$} which hold the amount of ball each ...
0
votes
0answers
33 views

Binary tree of Multipeg Tower of Hanoi

I've come across to this problem Show the solution of Multipeg tower of hanoi $(n,p) = (361,8)$ in a binary tree, where $n$ = number of disks, $p$ = number of pegs I know how multipeg tower of ...
0
votes
0answers
15 views

Minimizing sequential sum

For $S:=(s_i)_{i=1}^{n(k-1)+1},\,s_i\in\overline{R^-}$ for some natural numbers $n$ and $k$, define operation $T(j)S:=(s_1,\cdots,s_{j-1},\sum_{i=j}^k s_i,s_{j+k},\cdots,s_{n(k-1)+1})$ for $1\le j\le (...
0
votes
0answers
40 views

How do I approach this dynamic programming problem?

I have found this interesting dynamic-programming problem and want to know the approach . We are given an array 'a' of size-'n'. Each element of the array is either '1' or '2'. We start at index '0'...
0
votes
0answers
17 views

Dynamic Programming - How many properties must hold?

When reading about Dynamic Programming the two properties Overlapping Subproblems Optimal Substructure Are always mentioned. I am struggling to figure out whether or not these two properties are ...
0
votes
1answer
25 views

Contraction and $\max$ function

$f: \Bbb R \mapsto \Bbb R$ $g: \Bbb R \mapsto \Bbb R$ $h: \Bbb R \mapsto \Bbb R$ $h:=\max\{f(x), g(x)\}$ Is $h$ a contraction on $ \Bbb R$ if $f$ and $g$ are both so? First attempts of ...
1
vote
0answers
34 views

How can I find the minimum index of the array in this case?

We are given an array $a$ with $n$ values. Example: $[1,4,5,6,6]$ For each index $i$ of the array $a$ ,we construct a new array $b$ such that, $b[i]= [a[i]/1] + [a[i+1]/2] + [a[i+2]/3] + \cdots + [...
0
votes
0answers
13 views

Stochastic Control with non-continuous Scrap Value

Is there a way that the standard stochastic control problem with HJB equation applies also when the value function is given by $$ J(t,x,u) = max_{u(t)} \int_t^T f(x(s),u(s)) ds + g(x(T)) \\ s.t. dx_t= ...
1
vote
0answers
27 views

Solution to Average of Several Trails of Dicrete Time LQR with Noise

The solution to discrete time finite horizon LQR problem is well studied. We have the linear system $$x_{k+1}=A x_{k}+B u_{k}+w_k$$ where $w_k$ is a random variable with mean $0$ and finite second ...
1
vote
0answers
38 views

Linear quadratic regulator via least squares

In this set of slides, the finite horizon LQR problem is stated as a least-squares problem (slide 11), and using a naive method (e.g., QR factorization), the cost to solve this problem is $O(N^3nm^2)$ ...
0
votes
0answers
6 views

Maximal number of submatrixes in binary matrix

We have a matrix of size n x m. Elements of this matrix can be 0 or 1. We need to arrange submatrices of size 2 x 2 in such a matrix, but only with the condition that such matrices do not overlap and ...
0
votes
1answer
9 views

Closed form expression for simple 2D recurrence

It is given that $T(i,j) = T(i-1,j) + T(i,j-1)$ with boundary conditions $T(i,0)=T(0,j)=1$. Does there exist a closed-form mathematical expression for $T(n,n)$? I tried making a table of values of $T(...
0
votes
0answers
13 views

Complexity of A*-lasso algorithm (dynamic programming)

Consider Algorithm 1 in the Xiang & Kim (2013) paper known as A*-lasso for learning Bayesian Networks structure problem which is an NP-hard problem. It seems to me that Algorithm 1 has a ...
0
votes
0answers
31 views

Why is the Bellman principle of optimality considered a system of linear equations?

I am currently trying to understand why the Bellman Principle of Optimality is considered a system of linear equations. The Bellman optimality equation, taken from Reinforcement Learning - An ...
1
vote
1answer
95 views

How to generate the maximum cost path from source to destination vertex of a directed graph in linear time?

I was given a directed acyclic graph $G=(V,E)$ that has red and blue edges, and I want to generate a path from vertex $s$ to vertex $t$ such that the path has a maximum number of red edges. After ...
0
votes
1answer
37 views

Number of ways for getting sum equal to s using inclusion-exclusion

I am trying very hard to understand following inclusion-exclusion problem but can't get it. It will be very helpful if someone can provide detail explanation. f(s) is number of ways of having sum ...
0
votes
0answers
26 views

Q learning for more than one goal state

I have recently implemented a reinforcement learning (TD method) problem consisting of 19 states and 2 actions (Increase/decrease relative to previous time step action) with one goal state. Now I want ...
1
vote
1answer
40 views

Expected Value Iteratively picking divisors of number [closed]

You have a positive integer $n$ written on a blackboard, and you perform $k$ iterations of the following procedure: say the current number is $v$. Pick one of the divisors of $v$ (possibly 1 and $v$...
4
votes
1answer
58 views

Combinations of red and black balls

Given $N$ Identical Red balls and $M$ Identical Black balls, in how many ways we can arrange them such that not more than $K$ adjacent balls are of same color. Example : For $1$ Red ball and $1$ ...
2
votes
0answers
43 views

Card Expected Value with Option to Skip Cards

In a normal deck of cards, you can either reveal the top card or guess whether that card is black. If you reveal the top card, you get to see what the card is and the game continues with one less card ...
2
votes
1answer
40 views

Creating an Equation for my Online Store

I have a site that I am building and I am trying to figure out how much to charge customers. I want to go as low as possible while maintaining a certain profit margin. Here are the perimeters: I want ...
-1
votes
1answer
52 views

Inventory optimization problem.

I have n products. $(y_1, y_2, ...y_n)$ is my inventory vector. This should last for a certain period. Assume $m$ transactions will be made in this period. Each transaction will have only one of ...
1
vote
0answers
30 views

Resource Allocation Problem

Let $I, J, n \in \mathbb N$. Furthermore, let $\mathbf M \in \mathbb N^{I \times J}$. Finally, for $i \in \{1, \dots, I\}$ and $j \in \{1, \dots, J\}$, let $M(i,j)$ denote the element in the $i$th ...
1
vote
0answers
61 views

Finite Horizon Dynamic programming optimization (consumption-savings problem)

I am trying to solve this finite horizon dynamic problem (consumption-savings) using backward induction. Maximize $\sum_{t=0}^{T}u(c_{t})$ subject to $w_{0}>0, c\in [0,w],w(t+1)=(w_{t}-c_{t})(1+...
0
votes
0answers
17 views

stochastic dynamic programming - how to set up bellman and find FOCs

I have a function: $$ U = \mathbb{E} \bigg[ \sum_{t=0}^{\infty} \beta^t \ln c_t \bigg]$$ Where $0<\beta<1$ and my constraints are: $$c_t + k_{t+1} = \phi_t Ak_t^{\alpha}, 0<\alpha<1, k_1 =...
0
votes
0answers
15 views

Transition State for Dynamic Programming Problem

This is straight from the book: Optimization Methods in Finance. Overview The question is about how the transition state works from the example provided in the book. I attempted to trace through it ...
0
votes
0answers
52 views

Brackets around expression max value

I was working on a problem https://www.spoj.com/problems/LISA/ In the problem, the expression is given which has only operators (+,*). Putting brackets we need to get maximum value possible. First ...
1
vote
0answers
43 views

The expectation of the sum of an n-surface dice

Given an n-surface dice, the number on the $i_\text{th}$ surface is $v_i$, and the probability of facing upward of each surface is $p_i$ $v_i, p_i$ is all given integers, which is under mod of $...
0
votes
0answers
33 views

Memoization Confusion

Imagine the following game: There is a bank of numbers, and a target number. Players take turns selecting (and thereby removing) a number from the bank, and subtracting it from the target. The ...
0
votes
1answer
57 views

In Blackwell's condition for T to be a contraction mapping, we require that satisfies discounting. What is the intuition of discounting?

The discounting condition is as follow: There exists some $β∈(0,1)$ such that $[T(f+a)](x)≤(Tf)(x)+βa$, for all $f∈B(X),a≥0,x∈X$. While the monotonicity condition makes sense, I can't give a nice ...
1
vote
1answer
35 views

Trying to prove my solution to a game problem using MI

I've been thinking about a solution for a problem presented in a game. I intuitively understand why I think my solution is correct, but don't know how to prove it mathematically. The game goes like ...
0
votes
0answers
37 views

Explain recurrence and Dynamic Programming methods

Well during competitive programming, Dynamic Programming and Recursion is one of the most favorite topics. It kind of draws the line between an average and a good coder. Now my question is, is there ...
1
vote
0answers
30 views

Guess and verify: verification theorem for Hamilton-Jacobi-Bellman equation

Let $t \in [0,\infty)$ denote time, $x(t) \in X \subset \mathbb R_+$ the state and $u(t) \in \mathbb R_+$ the control. Consider the following optimal control Problem \begin{align} &V(x_0) = \max_{...
0
votes
1answer
35 views

Does the theory of Gittins Indices solve the Multi-armed Bandit problem?

For example, both Wikipedia and Reinforcement Learning: An Introduction (page 33) seem to claim as much, which would suggest that the problem has been solved for over 40 years. However, doing as ...
0
votes
0answers
58 views

Dynamic programming's principle of optimality as an abstract construct

In dynamic programming, the principle of optimality (refer to Bertsekas's Optimal Control, volume 1, page 18) is a statement that says: For any optimal policy $\pi$ , we always have a suboptimal ...
2
votes
1answer
117 views

Fake coin with weighing function [closed]

I have the following question: "There are n coins, all weight equally except one. In addition, we have a scale that can compare any s coins, for any s, with other s coins in the cost of w(s). The ...
0
votes
0answers
33 views

Lengths' relations of Longest Common Subsequence (LCS)

I am struggling with comparing about 1000 sequences (strings) and finding the lengths for all possible LCS. The problem is not an algorithm but a relationship between lengths of LSC. Based on what I ...
1
vote
0answers
20 views

Optimisation in public transport drivers behaviour

I am trying to model an optimisation problem. Here is the setting: The driver has to stop at each of the seven stations of the trip (They are ordered linearly so he first comes across station 1, then ...
1
vote
0answers
24 views

Equivalent formulations of stochastic HJB equation

I have some trouble understanding stochastic HJB equations. There are basically two forms of this equation that I have encountered in books, lecture notes etc... (one-dimensional case) 1) $rv(x)=\pi (...
0
votes
0answers
31 views

The limit point of a dynamical system

The dynamical system I have is given by $$p_{k+1} = \begin{cases}\left(1 - \frac{1}{n - (k+1)}\right)p_k + \frac{1}{n} & \text{if } p_k < \frac{n-k}{n} \\ \qquad\qquad p_k & \text{...
1
vote
0answers
62 views

Optimisation problem : How to solve a Knapsack problem with boolean variables? Is this problem considered a multi-choice Knapsack problem?

I am trying to solve an optimization problem, that it's very similar to the knapsack problem but it can not be solved using the dynamic programming. The problem I want to solve is very similar to this ...
1
vote
2answers
65 views

Number of binary strings of length $n$, where every $1$, if any, is followed by at most $k$ $0$s

This question is similar to the one asked here by another user, but I want to ask it again since it was worded poorly there and not enough context was provided. Actually, this question was asked as ...
0
votes
1answer
56 views

Confused between different form of Bellman equations mentioned in different literatures

I'm studying reinforcement learning from Prof. Andrew Ng's lecture notes. Here the Bellman equation is mentioned as following: $$V(s) = R(s) + \gamma\max_a\sum_{s'\in S}P(s'|s,a)V(s')$$ Note that ...
0
votes
0answers
34 views

Finding the closed form for the nth digit of a recurrence-relation on a word.

What methods can I use, beyond simple recursion, for computing recurrence relations of the form: $s_1 = A$ $s_2 = B$ $s_n = s_{n-2}s_{n-1}$ where A and B are strings and n is given? This is a ...
1
vote
2answers
59 views

Coin change with fixed denominations with duplicate values

Suppose I have $\{1, 1\} \{2, 2, 2\} \{5\} \{10\}$ coins. How many ways I can get 15 by adding coins? If I use DP then it counts 7, because $\{1+2+2+10\} \{1+2+2+10\} \{1+2+2+10\} \{1+2+2+10\} \{1+2+...