The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
27 views

Minimise cost for distributed file caching with distance search costs (Dynamic Programming)

I was hoping to get a bit of insight/a push in the right direction for the following problem: Given X number of slots, every slot is assigned a value for how much it would cost to place a copy of an ...
1
vote
0answers
10 views

Finding groups with minimum mean deviation

Is there any algorithm that groups consecutive elements in an array that gives the minimum mean deviation. For example we are given an array a=[1,2,3,4,8,2,3,5] There can be many "consecutive" ...
0
votes
0answers
21 views

Seam Carving - Energy functions. How do they work?

I have been taking an interesting in dynamic programming and more specifically Seam Carving. For those who are not aware what this is, please look here and for some more detailed information here. If ...
1
vote
1answer
39 views

Number of strings of size $k$ that do not have 'ab'

Consider $\Sigma = \{a,b,c\}$ and the language $L$, the set of all strings that do not contain 'ab' Find strings, of size $k$ is in $L$ ($L_k$) Consider $A_k$ (strings of size $k$ that end in $a$) ...
0
votes
1answer
35 views

What is the system equation $f$ in Hamilton equation in $H=g+p^Tf$?

I am studying the Donald Kirk's book Introduction to Dynamic Programming. Suppose some integral $\int g dt$ that must be minimised. Then you are given some constraints. Hamilton equation is $H=g+p^T ...
0
votes
1answer
28 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
1
vote
1answer
61 views

Cost of conversion of string $A$ to string $B$

We are given $2$ strings $A=[1 \dots m]$ and $B[1 \dots n]$ and the following $3$ operations are allowed: Insert a charachter,with cost $c_i$ Delete a character,with cost $c_d$ Replace a ...
1
vote
1answer
46 views

Arrange blocks to form matrix of $N \times 3$

Given are the blocks of 3 different colors (Red,Green and Blue). Red colored block of size $1 \times 3.$ Green colored block of size $1 \times 2.$ Blue colored block of size $1 \times 1.$ ...
3
votes
0answers
119 views

Finding optimal velocity profile using Dynamic Programming

This question has been asked on scicomp but I thought maybe it's more a mathematical problem of how Bellman's idea is to be applied here. The main problem for me is: How to introduce the time ...
0
votes
2answers
113 views

Longest Common Subsequence

Let $X=<x_1,x_2,…,x_m>$ and $Y=<y_1,y_2,…,y_n>$ be sequences and let $Z=<z_1,z_2,…,z_k>$ a longest common subsequence (LCS) of $X$ and $Y$.Then: If $x_m=y_n$,then $z_k=x_m=y_n$ and ...
0
votes
5answers
102 views

Number of ways in which $2010$ can be formed using $2,5,10$.

We can form $10$ using $2,5,10$ in $3$ ways. In how many ways can we form $2010(201*10)$. My teacher mentioned. $202*203/2$ I cannot figure out how. I also saw a DP method for finding number of ways ...
1
vote
2answers
64 views

number of combinations of selecting 1 element each from 3 sets..

Suppose we have 3 sets A=(a1,a2,...) B=(b1,b2,....) and C=(c1,c2,...) which may contain comman elements that is element present in set A may present in set B or in Set C,element in set B may be there ...
0
votes
0answers
36 views

Total number of subsets

I am trying to solve this hackerrank problem https://www.hackerrank.com/contests/101jul14/challenges/colorful-polygon. Not able to understand the editorial. Can some explain how to solve it using ...
1
vote
0answers
62 views

Traverse resultant 2d array after integer partition

I have used the solution of integer partitioning using dynamic programming explained in this post and in this article. Following is the resultant matrix when N is equal to 6: $$\begin{bmatrix} 1 ...
0
votes
2answers
50 views

Find point in 3D plane

I have four points in a 3D space, example: $$(0,0,1),\ (1,0,1),\ (1,0,2)\ \mbox{and}\ (0,0,2).$$ Then I have a 2D position on that square plane: $$x = 0.5,\ y = 0.5.$$ I need to find out the 3D ...
2
votes
0answers
80 views

Building Minimum warehouses

A big international retailer is setting up shop in India and plans to open stores in N towns (3 ≤ N ≤ 1000), denoted by 1, 2, . . . , N. There are direct routes connecting M pairs among these towns. ...
1
vote
0answers
27 views

Markov decision processes with action space only revealed at point of decision.

I have a problem which looks like a finite horizon Markov decision process, except the actions space at each time is revealed at the decision making point. There is no way to know before hand the ...
2
votes
3answers
35 views

Performing matrix chain multiplication by hand

I'm trying to gain intuition for writing a matrix chain multiplication algorithm by working through a few problems by hand. I see plenty of worked-through solutions on sets of three or four solutions, ...
2
votes
1answer
74 views

Dynamic Programming: Stock Exercise

I'm having a trouble dealing with this problem: Since future market prices, and the effect of large sales on these prices, are very hard to predict, brokerage firms use models of the market to ...
4
votes
1answer
84 views

Difference between Variation of Calculus problems and Control Theory problems?

Variation of Calculus seems to have problems without the control with variables such as state and time. Then again Control Theory problems seems to have problems with one extra variable that is ...
1
vote
0answers
31 views

How are Hamilton function and Hamilton-Jacobian-Bellman function related to each other?

I am trying to understand the solution to the problem 2 here that uses the Hamilton conditions for the HJB. I don't understand how the Hamilton conditions can be used with the ...
0
votes
1answer
71 views

hint to approach this question

2 teams play in total During the course of the game, each team gets points, and thus increases its score by 1. The initial score is 0 for both teams. The game ends when One of the teams gets 25 ...
0
votes
1answer
47 views

Count how many arrays of a specific type exist - O(N) Dynamic Programming

Consider an array of N + 2 binary digits (1 and 0), which contains at least one '1' and three '0'. The last and first digit of the array is 0. Given two numbers, let's say p and q, determine how many ...
0
votes
0answers
44 views

Recurrence Relation for the checkerboard problem

Im trying to come up with an accurate recurrence relation for the checkerboard problem given here (http://www.8bitavenue.com/2011/12/dynamic-programming-moving-on-a-checkerboard/). A recursive ...
2
votes
0answers
47 views

A Dynamic Programming Question

$\underline{\text{Household Sector:}}$ The household comprises of a single agent whose objective function is to maximize the expected value of his lifetime utility which is a function of ...
0
votes
0answers
66 views

Dynamic programming: optimal stopping problem

I am studying the optimal stopping problem. The probability setup is as follows: Assume space $\Omega=\{\omega\in C([0,T];R)|\ \omega_0 =0\}$. Denote $B$ as the canonical process and ...
0
votes
0answers
22 views

If the state variable retains all the history, is it still dynamic programming?

Let $X$ be a stochastic process observed over 100 periods. At each period, I seek the optimal control $u_t$ so as to minimize the total cost $$ V= \sum_{t=0}^{100} f\left(X_t,u_t\left(X_t, ...
1
vote
0answers
63 views

Dynamic Programming Question

A train is given to two children as a gift. A train consists of a sequence of cars connected in a single line. There is an even number of cars, and the two children wish to divide them up. They do ...
0
votes
0answers
130 views

The difference between Dynamic Optimization, Stochastic Programming, Optimal control and Markov Decision Processes

I've seen the following terms thrown around somewhat interchangeably, and I'm confused. What are the distinctions between them, and what are some representative problems that each deals with? ...
0
votes
0answers
71 views

Inventory Control using Dynamic Programming

I am trying to solve a traditional inventory control stochastic dynamic programming problem where \begin{align} x_{k+1} &= x_k + u_k - w_k\\ w_{N-1} &= \begin{cases} 0 &\text{w.p. } ...
1
vote
2answers
40 views

Another Grid Problem

There is a maze of size N*M, consisting of unit blocks. At the start Alice has K percentage of energy. Now Alice start from 1 st row and move towards N th row. From the present block she can move to a ...
1
vote
1answer
224 views

Reducing the maximum euclidean distance

This question comes from the HackerRank's "20/20 Hack February" contest which has now ended (problem link). There are N bikers present in a city (shaped as a grid) having M bikes. All the bikers ...
0
votes
0answers
29 views

Problems with understanding a few first order conditions in a Bellman Equation

I apologize for linking rather than posting the reference for my question, but it would take too long to write it in Latex here. Here it is a paper that I've been reading -- I did not understand the ...
3
votes
2answers
116 views

Flip the bulbs in minimum number of moves

We are given a $n \times m$ rectangular matrix in which every cell there is a light bulb, together with the information whether the bulb is ON or OFF. Now i am required to switch OFF all the bulbs ...
2
votes
1answer
59 views

Please explain why the below algorithm has n*m subproblems rather than 2(n+m-1) subprobems.

I am providing the solution as well which I found on the web. I don't understand why it says at the end that there are n*m subproblems. Question: For bit strings X = x1 . . . xm, Y = y1 . . . yn ...
0
votes
3answers
95 views

A dynamic dice game

I learned the following dice game from another forum. It was not solved there. The dice game is as follows. Toss 6 dice. Each toss you can keep one or more up to the total number of dice tossed. You ...
2
votes
2answers
105 views

Internet problem solving contest question

I am trying to solve a problem from the IPSC http://ipsc.ksp.sk/2001/real/problems/f.html It basically asks to compute the following recursion. ...
0
votes
0answers
32 views

Discrete Optimal Control and Monotone Policies

Let $x=(x1,x2) \in \mathbb{N}^2$ be the state, $u$ be the control, and the dynamics be given by $x^{(k+1)} = f(x^{(k)},u^{(k)},w^{(k)})$ where $w^{(k)}$ is an IID noise source. For some stage cost ...
2
votes
0answers
32 views

Dynamic programming and Lagrange multipliers

The problem is to solve dynamic programming problem $$\sum_{t=1}^T\left(\frac{t^3}{3}+\frac{t^2}{2}\right)a_t^2 \to \max$$ where $\sum_{t=1}^T a_t =c$, and $a_t$ is assumed to be $\geq 0$. It is ...
3
votes
1answer
217 views

Maximum subarray problem

Given a 2d array N*M made of only 1's and 0's . I need to find a maximum subarray(square or rectangle) between two rows of the given 2d array which has all ones inside it. I need to find count of ones ...
2
votes
0answers
180 views

Maximum Area of rectangle without any monsters

Given a rectangular grid of N*M (1-based indexing) in which their are k monsters on k different cells.Now we need to answer Q queries in which we will be given lowest row number(L) and highest row ...
0
votes
0answers
55 views

Open loop minimization for a inventory control system

I have read in a book (dynamic programming and optimal control by Bertsekas) that in case of inventory control system, with open loop minimization of the cost, we select all orders $u_0, \dots, ...
0
votes
1answer
177 views

Compute how to subdivide an n m marble slab to maximize your profit

You have mined a large slab of marble from your quarry. For simplicity, suppose the marble slab is a rectangle measuring n inches in height and m inches in width. You want to cut the slab into smaller ...
0
votes
0answers
56 views

A basic doubt on dynamic programming

In a book on dynamic programming the first paragraph of the introductory chapter says that "this book deals with situations where decisions are made in stages. The outcome of each decision is not ...
0
votes
1answer
80 views

Shortest path problem-minimal cost

Given a set of m things (1,2,...,m), we want to group them in clusters that contain adjacent things. For each cluster there is a cost $c_{ij}$. We are looking for the grouping in clusters so that the ...
0
votes
1answer
55 views

Help with probability formula in programming problem

I am trying to solve this dynamic programming problem using probabilities. I know how the recurrence for it should look but I have problems using a probability formula. I have the next case: In a ...
0
votes
0answers
120 views

Dynamic programming algorithm for GCD?

I can't seem to find a clear answer on this. I'm inclined to believe that there is not a DP solution for GCD, given the lack of information so far in my searches on the subject. I suppose that in ...
0
votes
0answers
629 views

Splitting an array into two subarrays with minimal sum

My question is if given an array,we have to split that into two sub-arrays such that the absolute difference between the sum of the two arrays is minimum with a condition that the difference between ...
0
votes
0answers
89 views

Minimum cost problem

I have been given $n$ points on a $2d$ plane. In terms of their $(x,y)$ coordinates. Now suppose I have to set, say firms, at these positions and the cost for building the first one is zero. For every ...
1
vote
1answer
158 views

Finding an optimal schedule [Dynamic Programming]

I'm reading through an algorithm textbook and I've come across yet another problem that I'm stuck on. I'm looking for some help solving it and if anyone could provide some similar, already-existing, ...