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
1answer
50 views

Stabilizing controls in linear quadratic regulator

I am studying a linear quadratic control problem with discounting. For $\gamma \in (0,1)$, $Q \succeq 0$ and $R \succ 0$ and linear dynamics $s_{t+1}=As_t + B a_t$, let the total cost starting in ...
0
votes
0answers
41 views

Dynamic programming with less decision variables than states

I'm trying to solve a dynamic programming problem with $n$ (continuous) state variables and only $1$ (continuous) decision variable, which affects all the states. For $n=1$ this is a standard problem ...
0
votes
1answer
27 views

Generate all possible sums of $N$ (with repetitions) [closed]

I want to get all possible sums out of numbers: $1, 3, 4$ that are equal to a given number $N$. There are some restriction: sequence order is important and algorithm cannot use recursion. For example, ...
0
votes
1answer
18 views

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 ...
0
votes
0answers
19 views

How to convert a function to separable form?

I am reading the book, "Introduction to dynamic programming", by Leon Cooper. In the first chapter they define a separable function as A separable function is one in which the function consists of ...
0
votes
0answers
10 views

MDP tabular setting.

I would be very curious to know if in the tabular MDP setting we have: $$ E_{\tau_1,\cdots, \tau_{N} \sim P^{\pi}_{\mu}} (1_{A}) = E_{s_1,\cdots,s_{N \times H} \sim d^{\pi}_{\mu}} E_{a_1 \sim \pi(.|...
0
votes
0answers
14 views

Box sorting Algorithm proof

i wrote a different proof for the box sorting algorithm in O(n^2) and proved it by induction. can someone please refute/provide another proof to the solution? The Problem- You are given a set of n ...
0
votes
1answer
37 views

How can i find the solution of this NP-hard optimization problem?

I have an NP-Hard optimization problem of the form: \begin{align} & \min {{\sum\limits_{i=1}^{M}{{{a}_{i}}}}_{{}}} \\ & s.t{{.}\:\:\:\:_{{}}}{{_{{}}}_{{}}}\sum\limits_{i=1}^{M}{{{a}_{i}}{{...
0
votes
2answers
42 views

Square matrix 0 x 0?

Can you consider a 0x0 matrix as a square matrix, I can't find the precise definition. I need it for my programming assignment for throwing exceptions.
0
votes
0answers
26 views

Optimal strategy for a dice game with an element of choice

This was given as part of an assignment on dynamic programming using Bellman equations, but I feel like it could also be solved purely in terms of probability. (I've already submitted the assignment, ...
0
votes
1answer
42 views

DP solution of choosing a subset k of n input numbers, “maximising the spread”

Mechanical engineer here with little to no formal training in optimisation. Recently though, I've spent some time looking into optimisation and dynamic programming due to a problem I wanted to solve ...
0
votes
1answer
23 views

Is Levenshtein distance related to largest common subsequence?

I don't have proof but i have gut feeling that , suppose s1 is string which needs to be converted to s2 then we can keep the largest common subsequence in s1 as it is and edit distance is number of ...
-2
votes
0answers
21 views

'The Intriguing Obsession' Codeforces Round #439 (Div. 2), 869 C

The solution given in the editorial used pnc to solve the above question. But I was trying to solve the question using dynamic programming,i.e, making a recursion for the above problem. So how can we ...
0
votes
1answer
13 views

Minimum cost in a 2D matrix

In my last interview, I was asked a question for which optimal approach I am still not able to figure out. Given a 2D matrix, with n rows and ...
0
votes
0answers
72 views

0-1 Knapsack problem based on largest index

I understand that the commonly taught solution to the problem is based on the question of whether the last item should be included in the optimal solution that would result in two cases in which we ...
0
votes
0answers
31 views

Corner Solution To A Recursive, Strictly Concave Function?

I was reading through Dynamic Programming by Richard Bellman today, and I got to exercise 7 in chapter one. You are asked to prove a theorem, but I feel like the theorem itself is... well, not quite ...
1
vote
0answers
9 views

How to combine sites with some limitation?

I have a dataset from a real clinical trial. This is the virtual sample: ...
0
votes
1answer
47 views

Can we see optimization problem as functions?

I have optimization that goes the followings: \begin{equation} \begin{aligned} &\max_{x_1,\dots,x_k} &&f_1(x_1)+f_2(x_2)+\dots+f_k(x_k)\\ &\text{subject to} &&x_1 + \dots + ...
0
votes
1answer
23 views

Minimum step to reach from 1 to n.

What will be the minimum number of steps to reach n from 1 if from any position p we can move to position p * i where i > 1 and i < 6 ? Can this problem be solved using a greedy technique instead ...
1
vote
0answers
28 views

Optimal worst case strategy for card game - double if red, half if black

Flip cards in a shuffled deck. Win double if red, lose half if black. You can choose whether to bet or not each time. What’s the optimal worst case scenario strategy? Start by considering a situation ...
0
votes
1answer
17 views

Can the weighting matrices in LQR be a function of the states instead of time?

In LQR, the cost has the following form: $$ J = x(t_f)^T Q(t_f)x(t_f) + \int_0^{t_f} \big( x(\tau)^TQ(\tau)x(\tau) + u(\tau)^T R(\tau)u(\tau) \big) d\tau$$ where $x$ is the state vector and $u$ is ...
0
votes
0answers
34 views

I Need Helping Understanding a Case of this Recurrence Relation. I am Stumped

I came across this question in my textbook and it is stumping me. Namely, what is stumping me is the final two cases when creating the recurrance relation. I sort of understand that you have to take ...
2
votes
1answer
107 views

Expansion of $(a+b+c+d+e+…)^n$, but with all coefficients equal to 1.

I'm looking for a formula to calculate the sum of $(a+b+c+d+...)^n$ but with coefficients equal to 1. For example in $(a+b+c)^2$. I want the sum of $a^2 + b^2 + c^2 + ab + bc + ca$. And for $(a+b+c+d)^...
0
votes
0answers
21 views

possible sum of product of k elements from array(repetitive allowed)

Given an array of n elements and a number k we have to select k elements from array and calculate sum of all possible product obtained by these k elements (repetitive allowed); Also two set of k ...
0
votes
0answers
7 views

Dynamic programming with three-period relation

suppose my choice variable is $c_{t}$ and state variable $k_{t}$. I want to make an infinite-horizon problem, where $c_{t}$ not only matters for $k_{t+1}$ but also $k_{t+2}$. For example, a dynamics ...
0
votes
2answers
37 views

Algorithm for a min cost problem

Given are $n$ people who arrive at point $p$. They all need transport by bus to point $q$. Every bus trip from $p$ to $q$ has a cost of $K$, no matter how many people are inside the bus. The arrival ...
1
vote
1answer
46 views

Finding if two sequence M and N are in the shuffle product of W and Z while not knowing W and Z

I have to solve this problem using dynamic programming but I'm stuck. We have to sequence W and Z. Let's assume for now that: W = ACA and Z = GT their shuffle product is W ⧢ Z = {GTACA, GATCA, GACTA,...
0
votes
0answers
17 views

Finding the count of subarray that sum to a given integer

https://leetcode.com/problems/subarray-sum-equals-k/ I was doing this coding question and I haven't been able to find an intuition as to using the hash map method to solve it. The solution is ...
1
vote
0answers
35 views

Dynamic Programming and Hamiltonian problem

Consider the following infinite-horizon optimal control problem for a firm in continuous time. At any moment $t \geq 0$, let $s(t) \in [0, 1]$ be the relative size of the market for the firm’s product....
0
votes
0answers
7 views

How to interpret changing constants in a HJB?

So when the changes to a state variable depends on a constant $w_{t}$, eg $dG_{t} = w_{t}*\pi_{t}$, on a finite interval [0, T], how can I compare the two value functions when I change the constants $\...
0
votes
2answers
63 views

calculating total number of allowable paths

I seem to be struggling with the following type of path questions Consider paths starting at $(0, 0)$ with allowable steps (i) from $(x,y)$ to $(x+1,y+2)$, (ii) from $(x,y)$ to $(x+2,y+1)$, (iii)...
0
votes
1answer
47 views

Shortest Path Passing Through All Points When Start and End Points are Given

Assume we have a set of points $\{A,B,C,\dots,Z\}$ in a plane. What is the shortest path which includes all points once, starts at $A$ and ends in $Z$ and $A \ne Z$ I am trying to identify if this ...
0
votes
1answer
31 views

Dynamic Programming Cheapest Train Ride Question

I am struggling with the below dynamic programming practice problem and I am hoping someone can help. The problem states: "You want to go from station 1 to station n by rail. The train fare from ...
0
votes
0answers
12 views

Dynamic Programming minimal costs algorithm

I am looking for an algorithm for the following problem: Given that we need to bake n>5 cakes. We can either decide to bake the cake ourselves or we can choose to let someone else bake the cake. ...
0
votes
1answer
39 views

How can I calculate the minimum number of moves needed in a game involving stacks?

I'm currently programming a game, and I have been stuck on the following problem for a while. The above figure is a set of stacks. The end-goal is to sort all items by color in the least possible ...
1
vote
2answers
37 views

Solving Knapsack with Multiple Constraints and Return nth Best Results

Example Data For this question, let's assume the following items: Items: Apple, Banana, Carrot, Steak, Onion Values: 2, 2, 4, 5, 3 Weights: 3, 1, 3, 4, 2 Max Weight: 7 Objective: My goal is to ...
0
votes
2answers
39 views

How to identify mathematical model of “Fuel Problem”?

Fuel problem My vehicle's tank has unlimited capacity of some units (galons or liters) , but it is broken and the gasoline evaporates from it if. So, if I don't consume the gasoline I have bought ...
1
vote
0answers
28 views

Computing an average of many sums by dynamic programming (?)

Let $N$ be a large integer, let $x_1, \ldots, x_{2N}$ be a subset of some space $\mathcal{X}$ (the details of which are irrelevant), and let $f, g, h$ be functions mapping $\mathcal{X}$ to $(0, \infty)...
1
vote
1answer
17 views

Dynamic Time Warping

The dynamic time warping algorithm provides a notion of distance between two trajectories $s$ and $t$ with points indexed by $s_i$ and $t_j$. The dynamic programming algorithm is only a few lines and ...
0
votes
0answers
15 views

$\varepsilon$-optimal policy and percentage of optimal

If a question asks for a policy that is within 1% of optimal, then would that mean $\varepsilon = 0.01$?
0
votes
1answer
29 views

How to solve the optimality equation? (Markov decision process)

I'm struggling with this problem I have to solve, I have attached the problem below. I have done some questions that are similar but I have given simple values for 'a' and 's'. If someone could help ...
2
votes
1answer
50 views

Dynamic programming algorithm

I'm attempting to solve the following problem: Balls are falling from the sky. We know at which location (on a straight line) will each ball drop, and we know the time (in seconds) at which ...
4
votes
0answers
215 views

Need help solving a min-max fixed point equation

I have the following fixed point equation: for all $p\in[0,1]$ $$V(p) = \min_{\lambda_1,\lambda_2\in[0,1]}\max\{pr,(1-p)r,\beta\mathbb{E}_{a,y'}[V(f_{\lambda=(\lambda_1,\lambda_2)}(p,a,y'))]\}$$ ...
0
votes
1answer
26 views

Knapsack Problem (Optimal solution through Dynamic Programming): When limit is less than the nth (or ith) weight and purpose of max?

I am trying to understand the knapsack problem from the book: Algorithm Design Equation (1) deals only with the case when nth item is too big. But why in the “Otherwise” case we have included the ...
0
votes
1answer
26 views

Knapsack Problem using Dynamic Programming: Mathematical Equation

I am trying to understand the knapsack problem from the book: Algorithm Design I can’t understand the following equation. This provides solution to knapsack problem in the context of Dynamic ...
0
votes
0answers
23 views

Optimal substructure of rod cutting?

How do you show the optimal substructure of the rod cutting problem(defined as in https://cs.stackexchange.com/q/97674). I am trying to follow the guideline steps So suppose someone told us one of ...
0
votes
0answers
15 views

Optimal strategy for tossing three dependent coins

Suppose that I have three correlated coins. The marginal probability of Head of coin $i$ is denoted by $p_i$. The conditional probability of head for coin $i$ given the outcomes of coin $j$ and $k$ ...
0
votes
2answers
46 views

Probability of getting certain number of points

A one on one basketball tournament is happening in your community. Each game has a point system. 3 points for a win, 1 point for a tie, and 0 points for a loss. You have a 50% chance on winning, 40%...
0
votes
1answer
24 views

Suggestion over book on optimal strategies

I am looking for a book explaining me theory and practice of problems common in interviews as: ...
0
votes
0answers
10 views

Proving existence of an optimal path with an added property

Given is a sequence of "A-points" $A_1,\dots,A_k$ on a grid, and we have to give an optimal path, i.e. a sequence of points $P_1,\dots,P_k$ such that $P_i$ and $P_{i+1}$ share a row or column, and $\...

1
2 3 4 5
9