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.

learn more… | top users | synonyms

-2
votes
0answers
7 views

Solution manual of MDP: Discrete Stochastic Dynamic Programming?

Do you know where can I get the solution to the problem sets of the book: Martin Puterman, "Markov decision processes: discrete stochastic dynamic programming". The solution manual can be very ...
2
votes
1answer
18 views

How to do continuous-time Bayesian updating?

I am reading a game theory lecture notes. Some parts involve a continuous time Bayesian updating computation which I didn't really understand. There are two states $\{Good,Bad\}$. At time t people ...
1
vote
3answers
39 views

Finding the formula for summation of the series

I was just solving a competitive programming question, wherein I found out that a formula can be used for solving it efficiently. Problem statement: http://www.spoj.com/problems/TOHU/ I tried a lot to ...
0
votes
0answers
16 views

Approach for this Popular Algorithmic Problem

Given a matrix we have to select one value from each row so that the total value cost selected is minimum. Now the problem is we cannot select column "0" to "J" in "I"th row if we have selected ...
2
votes
1answer
48 views
+100

Integrate two sets of Data and check similarity

I have the following CSV Data I used Excel Charts to plot the Data I want to compare these Data with other Data, in another word i want to comapre 2 curves and check the similarity between them in ...
0
votes
2answers
42 views

Minimize a non-convex function subject to linear dynamics constraint

I want to solve the following problem: $$\min\limits_{\bf u} \frac{\bf c^T {\bf x} (T_f)}{\| \bf c\|\|{\bf x} (T_f)\|}$$ subject to $$\dot{\bf x} (t) = A {\bf x}(t) + B {\bf u}(t)$$ $$x(0) = x_0$$ ...
2
votes
1answer
18 views

Explanation of strategies in infinite horizon dynamic programming problem

My question is regarding the Bellman equation regarding strategy $\sigma^{(1)}$ on the last 2 lines (I have attached pictures of the book below). If we know that all future states will have value of ...
1
vote
0answers
12 views

Scheduling problem

Consider the following setting: $N$ jobs, each has a starting time, which is assumed to be a natural number and all N numbers are distinct, e.g., the 1st job has starting time at 5, the 2nd is 6, the ...
0
votes
0answers
12 views

Pyramidal TSP without weight

Say $G=(V,E)$ with $V=\{1,...n\}$ and $l(i,j)$ is the distance of arc $(i,j) \in E$. The aim is to find a pyramidal path in $V$ with minimal length. A pyramidal path is a sequence of vertices $(n,i_1, ...
0
votes
0answers
16 views

Greedy choice property

There are two versions of the Knapsack problem, the integer and the fractional one. The difference between the integer and the fractional version of the Knapsack problem is the following: At the ...
0
votes
1answer
57 views

Maximize profit with dynamic programming

I have 3 tables… $$\begin{array}{rrr} \text{quantity} & \text{expense} & \text{profit}\\ \hline 0 & 0 & 0 \\ 1 & 100 & 200 \\ 2 & 200 & 450 \\ 3 & 300 & 700 ...
-1
votes
0answers
32 views

The minimum number of machines to install the software on to clean the entire network

A Worm has affected all computers in a companies LAN network. The worm removal software is licensed in such a way that only adjacent machines (connected directly by a cable) can share a copy of the ...
-6
votes
1answer
211 views

Are the propositions right?

I want to choose if the following propositions are true or false and justify the reason for the choice. Polynomial: good, exponential: bad. Radix Sort works correctly if we use any right sorting ...
3
votes
1answer
62 views

Count connected components after $M$ marbles removed

There are $N$ marbles in a line, numbered $1$ through $N$ from left to right. We need to count numbers of ways to remove exactly $M$ marbles such that there are exactly $C$ remaining connected ...
0
votes
0answers
31 views

Setting up the Bellman equations for dynamic programming

I have the following question I want to understand. The owner of a chain of three grocery stores has purchased five crates of fresh strawberries. The estimated probability distribution of ...
2
votes
1answer
61 views

Why does the Hamilton Jacobi Bellman Equation imply Pontryagin's Minimum Principle

I'm having difficulty understanding the proof that allows us to go from the Hamilton-Jacobi-Bellman equation to to the Pontryagin Min(Max) Principle. Lets consider $x(t)$ and $u(t)$ as real valued ...
2
votes
0answers
22 views

Reducing a Knapsack-type problem to a known problem

The Quadratic Knapsack problem, introduced by Gallo, is an optimization problem in the following form: $max \sum_{i=1}^n{\sum_{j=1}^n{q_{ij}x_ix_j}}$ $s.t \sum_{i=1}^n{w_ix_i} \leq c$ $x \in \{0, ...
0
votes
1answer
22 views

Optimal schedule for a set of jobs

Assume that yo have a set of jobs in which each has only a processing time that you need to minimize the sum of the completion (finish) times. Prove that your schedule is optimal. The wording throws ...
0
votes
1answer
103 views

Cost function with stochastic variable

I'm not as well versed as I would like to be to confidently evaluate the following cost function. So any affirmation would be appreciated. Given an initial stage $x_0$ $$J_\pi(x_0) = \lim_{N \to ...
1
vote
1answer
233 views

Minimum cost to convert string S to good string

Given a string $S$ of $0$ and $1$ we need to convert it into a good string. A string is called good if and only if : Their are no two or more $0s$ or $1s$ together. It means $001$ is not good but ...
0
votes
2answers
46 views

Dynamic Programming Investment Question

I'm working on a dynamic programming problem from a textbook. My solution is different from that given in the solution manual, and I'm looking for input as to which answer is correct. The problem is ...
0
votes
0answers
7 views

Minimizing handling costs in the one-to-one TSPPD

Currently I'm reading about the Traveling Salesman Problem with Pickups and deliveries. This is similar to the classical TSP but there are $n$ requests and each request has a pickup location and a ...
0
votes
0answers
45 views

Define a maximization problem as an optimal stopping problem

We work over $\mathbb{R}_+^L$. Let $V$ be the set of vectors whose coordinates take values $0$ or $1$. Let $\mathbf{w}(t)$ (in $\mathbb{R}_+^L$) a vector that changes each time slot. To each vector ...
4
votes
1answer
84 views

Expected outcome for repeated dice rolls with dice fixing

Here is another dice roll question. The rules You start with n dice, and roll all of them. You select one or more dice and fix them, i.e. their value will not ...
0
votes
1answer
31 views

Computing time-complexity of DP recursion

I've written an algorithm which uses 3-dimensional DP table and it goes as follows: $DP[i][j][0]$ can be computed in $O(1)$ for any $i,j$ and $DP[i][j][k]=\max(DP[i][m][0]+DP[m+1][j][k-1]) $ for all ...
2
votes
5answers
422 views

Find value of f(2013)?

Given a function $f(x)$ such that: $f(1) + f(2) + f(3)+\cdots+f(n) = n^2f(n)$ Find the value of $f(2013)$. It is given that $f(1) = 2014$. I tried attempting the question as a bottom-up DP, but ...
1
vote
2answers
88 views

Dynamic programming:Making a Change

I'm practicing problems on dynamic programming.The problem is as follows: You are given n types of coin denominations of values v(1) < v(2) < ... < v(n) (all integers). Assume v(1) = 1, so ...
0
votes
0answers
10 views

Dinamic programming for sum of two largest values from a Uniform parent

I must find a recursion formula to find the sum of two largest values from a Uniform parent [0,1]. I need dinamic programming but I don't know how to organize it.
0
votes
0answers
52 views

Dynamic programming for optimal maximum and optimal minimum

We have a sequence of $a_i$ and a choosing rule that is take the first number $x_t\ge a_t$. The definition is = $$ min\{ t|t \in \{ 1,2,\cdots,n\}\,\,,\,\, x_t\ge a_t\}$$ The sequence $a_i$ is ...
1
vote
1answer
32 views

What is the formal name of this problem?

I'm doing an assignment and I'm having trouble with this question, could anyone give me the formal name of the problem described so I can research it better? The task is to move a player along a path ...
1
vote
2answers
375 views

Algorithm: Scheduling of Overlapping Intervals

I'm reviewing algorithms, and I've come across this problem. At first, it seemed like an interval scheduling problem to me, but now I think it is a dynamic programming problem. I'm not sure how to ...
1
vote
1answer
104 views

Three dynamic programming techniques

I've noticed three terms that come up when I look at dynamic programming exercises. Binary choice - seen it in a weighted interval scheduling problem. Multiway choice - seen in a segmented least ...
0
votes
1answer
23 views

Finding the optimal solution

Find the optimal solution of the problem $$\min \Bigg \{ \int_0^1 [x^\prime (t)^2 + 2x(t)^2]e^t dt : x(0) = 0, x(1) = e - e^{-2}\Bigg \}$$ and the value of the minimum. Not sure how to approach this ...
1
vote
1answer
61 views

Can every optimization problem that can be solved by a greedy algorithm be solved using dynamic programming? Why, why not?

In other terms, is the set of optimization problems solvable using greedy algorithms contained fully within the set of optimization problems solvable by dynamic programming?
0
votes
1answer
87 views

Understanding Mathematical Symbols in Algorithms

Just a quick question here. I am working on an assignment for algorithms involving dynamic programming. Don't worry, this isn't a question about my assignment, just a question about understanding a ...
1
vote
1answer
65 views

How to convert mathematical programming problem to dynamic programming problem

Do not know how to approach this problem. The task is to convert the problem of mathematical programming: $\max(\prod_{i=1}^nx_i)$ $\sum_{i=1}^na_ix_i\leq c$ $c \gt 0, a_i \gt 0$ into a problem ...
1
vote
1answer
69 views

Dynamic Programming - how to minimize sum of distances

Let's assume that we're given the num[N], an array of N positive integers in an ascending order. For instance, let's assume that N=10, and num[N] is the following: 1 2 3 6 7 9 11 22 44 50 Let ...
1
vote
0answers
18 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
27 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
45 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
37 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
157 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
83 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
71 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
149 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
121 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
105 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
92 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
46 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
73 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} ...