Questions about problems that can be solved by combining recursively obtained solutions of subproblems.

learn more… | top users | synonyms

0
votes
1answer
41 views

State of variables in dynammic programming

I would like to know what a state variable is in simple words, and I need to give a lecture about it. I have chosen the Longest Common Subsequence problem I found a similar question but it has no ...
1
vote
2answers
54 views

Edit distance (Levenshtein-Distance) algorithm explanation

I want to calculate the edit distance (aka Levenshtein-Distance) between two words: «solo» and «oslo». According to this site we'll get the result matrix: What I don't understand is: In case of ...
-1
votes
0answers
25 views

State of optimal substructure? [closed]

My teacher has told me that I need to do the proof of the optimal substructure exaplaining the "state". I have no idea what a state is . I have chosen the matrix chain product as a dynamic programming ...
3
votes
1answer
37 views

Does FACTORING have optimal substructure or analog to it?

Is there any approach to FACTORING that can leverage optimal substructure allowing the problem to be decomposed into smaller subproblems? That is, perhaps being unnecessarily verbose, until an easily ...
1
vote
0answers
30 views

Palstar algorithm Dynamic Programming getting the result [closed]

I recently started to read abour dynamic programming, and I am doing an exercise on it. The problem to solve: Given a String, find the least amount of palindromes it can be split into, and print out ...
2
votes
1answer
54 views

Arrangement of numbers in a grid

I have a $n \times m$ matrix $M$ and a permutation of sequence $P$ of numbers from $1$ to $n$. I have to fill the matrix using numbers $1$ to $n \times m$ in such a way that for each row $i$, the ...
1
vote
2answers
53 views

Proof of an Optimal substructure in Dynammic Programming?

Could someone please explain how exactly the proof of optimal substructure property in dynamic programing problems works?, they usually say that " let's say the global optimal solution is A, and B is ...
2
votes
2answers
96 views

How Dynamic programming can be used for Coin Change problem?

As far as I can unserstand Dynamic programming stands simply for memoization (which is a fancy name for lazy evaluation or plain "caching"). Now, I read that there is we can reduce complexity of ...
0
votes
1answer
40 views

Dynamic Programming Solution to 0,1 KnapSack Problem

I am trying to understand the DP solution to the basic knapsack problem.However even after reading through a variety of tutorials ,its still beyond my comprehension.I am taking an algorithmics course ...
-2
votes
1answer
18 views

why negative cycle exists if we can relax the edges one more time after running the Bellman Ford Algorithm

We know Bellman Ford is an algorithm to find the negative cycle. And here is the algorithm for Bellman Ford Input: Given a graph G(V,E) and w(e) is weight Output: Return Yes if negative cycle exists. ...
3
votes
1answer
51 views

How do I reconstruct the forest of syntax trees from the Earley vector?

Using the Earley vector as a recognizer is quite straightforward: when the end of the string is reached, you just have to check for a completed axiomatic production started at position 0. If you have ...
1
vote
0answers
36 views

Dynamic Programming - Seemingly unnecessary recursion?

I am working on my thesis on revenue management. I have been over the following problem multiple times now, but I fail to see where my mistake is. This example is based on The Theory and Practice of ...
3
votes
1answer
71 views

Fast algorithm for matrix chain multiplication in special case

An exercise from the book Foundations of Algorithms Using Java Pseudocode: Write an efficient algorithm that will find an optimal order for multiplying $n$ matrices $A_1 \times A_2 \times \ldots ...
5
votes
1answer
65 views

Maximum sub-matrix sum

Given a $n\times m$ matrix $A$ of integers, find a sub-matrix whose sum is maximal. If there is one row only or one column only, then this is equivalent to finding a maximum sub-array. The 1D version ...
1
vote
1answer
41 views

How to modify Bellman-Ford algorithm for this specific Minimum Cost Flow problem?

I'm trying to design an algorithm for the following optimization problem. Suppose that $G=(V, E)$ is a digraph where $V$ and $E$ are sets of vertices and edges of $G$, respectively. $|V| = n$ and $|E| ...
2
votes
2answers
184 views

The Gas Station Problem - fast implementation

Recently I was asking about the algorithm to solve The Gas Station Problem and I got useful answer. Unfortunately solution with transforming a graph to complete graph and then preparing another one to ...
1
vote
0answers
50 views

Algorithm for keeping the Maximum and allowing Splits of Strings/sequences

The problem is as follows: Given $k$ strings of size $n$, propose a data structure to support the following operations: Return the maximum of a string. Given an index $i$, and $2$ strings $a$ and ...
0
votes
1answer
39 views

Finding dynamic programing algorithm

I got a matrix of integers of size $3\times n$. Of each one of the three rows, for each column I got to choose one number, with the restriction that, for each $i$, the numbers chosen in the $i$th and ...
0
votes
2answers
82 views

Maximum Value Contiguous Subsequence [closed]

I have stumbled upon this problem online: Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i)... > A(j) for which the sum of elements in the subsequence is ...
0
votes
1answer
44 views

Zigzag subsequence [closed]

As part of a homework assignment I'm asked to describe an O(mn) algorithm to find the length of the longest zig-zag sub sequence. The overall topic for this assignment is dynamic programming. As ...
0
votes
1answer
47 views

Dynamic programming rectangular grid [closed]

You are given a 40x40 grid. Each point of the grid is either 0 or 1. You are also given an infinite amount of 1x40 rectangular slabs. How to find out the minimum number of slabs required to cover all ...
0
votes
1answer
93 views

Help with a dynamic programming solution to a pipe cutting problem

I'm trying to complete a problem where I have to design and implement a dynamic programming solution to the following problem You have to cut a metal pipe into several pieces. To do so, you bring ...
3
votes
3answers
306 views

Can't understand why the DP Subset Sum algorithm is not polynomial

I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial. Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the ...
1
vote
1answer
87 views

Studying Skiena. War Story: What’s Past is Prolog

I am reading The Algorithm Design Manual, 2nd Edition. The book gives an example task and then explains how to solve it step by step. (The task and solution is detailed here) But I don't follow one ...
1
vote
1answer
90 views

Knapsack problem, partition problem, or in general dynamic algorithm with negative numbers allowed [closed]

How to think about dynamic algorithms which allows negative integers in input (where it's problematic, because obviously it's not always the case)? Examples: Partition Problem with negative numbers ...
8
votes
6answers
2k views

How is Dynamic programming different from Brute force

I was reading up on Dynamic Programming when I came across the following quote A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best ...
1
vote
1answer
120 views

Dynamic programming VS Greedy Algroithms [closed]

I have two True or False questions in my practice test that are related but I am unsure about: ...
1
vote
1answer
19 views

Explain BadNeighbors problem statement

I was solving a problem on topcoder http://community.topcoder.com/stat?c=problem_statement&pm=2402&rd=5009 . There is one example : ...
4
votes
3answers
128 views

Are there dynamic programming examples that run in exponential time?

Are there dynamic programming examples that run in exponential time? Every example that I've seen so far constructs the top half of a matrix in a bottom-up fashion ($n^2$) from the base case and ...
3
votes
2answers
106 views

minimizing the summed cardinality of set unions

this optimization problem, I am working on, is kind of making me crazy. ;) Given is a list o of sets (with finite cardinality) of strictly positive integer values ...
0
votes
1answer
62 views

Updating maximum sum subrectangle in a sparse matrix when one element is changed

I have an m x n matrix which is sparse with N non-zero entries. A modified version of Kadane's 2-d algorithm can find the maximum sum subrectangle in O(m N log n) time, which beats traditional ...
1
vote
1answer
88 views

Minimum number that cannot be formed by any subset of an array

We have an array of Integers, $A[]$ and we have to find the minimum number that is not the sum of a subset of array using the elements from $L$ to $R$ indices. I was thinking of using coin change DP ...
3
votes
1answer
111 views

Viterbi algorithm recursive justification

I have a question regarding recursion in Viterbi algorithm. Define $\pi(k; u; v)$ which is the maximum probability for any sequence of length $k$, ending in the tag bigram $(u; v)$. The base case ...
-1
votes
1answer
86 views

Finding number of maximum independent sets in tree, using dynamic programming

I'm quite stuck trying to answer this. The problem of finding the size of the maximum independent set in a tree using dynamic programming is well documented and many solutions are around. I've been ...
0
votes
0answers
36 views

Help in developing a dynamic programming solution to this problem

I have asked this question on programmers.stackexchange but nobody was able to answer this question.I have asked for help on other forums but did not get much help.Since this is a part of my research ...
2
votes
1answer
415 views

Variant of the knapsack problem

How would you approach the knapsack problem in a dynamic programming situation if you now have to limit the number of item in the knapsack by a constant $p$ ? This is the same problem (max weight of ...
6
votes
3answers
407 views

What is “dynamic” about dynamic programming?

One of my seniors had a job interview and he was asked why it is called dynamic. He couldn't answer and after he gave up the interviewer said that there's nothing dynamic about it, its just called ...
1
vote
1answer
223 views

Dynamic subtraction game

I came across the following dynamic subtraction game: There is one pile of n chips. The first player to move may remove as many chips as desired, at least one chip but not the whole pile. ...
0
votes
0answers
103 views

Traveling Salesman with Held and Karp Algorithm

I am well aware of the DP solution to the traveling salesman problem; also known as the Held and Karp algorithm for TSP. I have implemented it with bitmask, and it's something like this: ...
1
vote
0answers
220 views

minimum cost path

Consider the following problem: There are $n$ points in the plane. Starting from one of them I want to visit each of them once (except the starting node which has to be visited twice) but in a way ...
3
votes
1answer
83 views

exact matching between two strings - linear edit distance?

This is the problem, given a string with characters from: a-z, ., *, and another string with ...
-1
votes
1answer
223 views

How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n

How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n ? for example : for n=10 1 2 3 4 10 20 30 40 100 200 the sub-sequence of length ...
4
votes
1answer
94 views

Find equidistant triplets in a tree

Given a tree $T$ with $n$ vertices, we want to find the number of triplets of vertices $(a,b,c)$ such $d(a,b) = d(b,c) = d(c,a)$ where $d$ is the distance function (length of the shortest path between ...
4
votes
1answer
419 views

Algorithm for splitting array into subarrays with sums close to the target value

I have an array of positive integers, $A = (a_1, a_2, ..., a_n)$. Let $s(A)$ denote the sum of elements of array $A$. I also have an integer $t$, such that $1 < t \le s(A)$. I want to split the ...
0
votes
1answer
87 views

Count the number of integers satisfying two conditions using DP

Given two integers $n$ and $m$, how many numbers exist such that all integers have all digits from $0$ to $n-1$, the difference between two adjacent digits is exactly $1$, and the number of digits in ...
2
votes
1answer
744 views

Understand the time complexity for this LCS (longest common subsequence) solution

I would appreciate an intuitive way to find the time complexity of dynamic programming problems. Can anyone explain me “#subproblems * time/subproblem”? I am not able to grok it. Code for LCS - ...
2
votes
1answer
28 views

Optimal coverage of a $D$-dimensional grid with small blocks

I have a $D$-dimensional grid with the size $(N_1, \ldots, N_D)$, where $N_i$ are natural numbers, and a "flat block size" $M$, also a natural number. I want to find a decomposition $(m_1, \ldots, ...
1
vote
2answers
197 views

A complicated variant of Weighted Median problem

Suppose, we have an array of numbers $x_j$ and their corresponding weights $w_j$ where $\sum_j w_j \gt 1$. Now we need to find $x_m$ such that $$\sum_{j=1}^{m-1} w_j \lt 1/2 \quad \text{and} \quad ...
1
vote
0answers
172 views

Writing a program to find the optimal reward for a 2-armed Bernoulli bandit

(It might be useful to refer to page 9 of Multi-Armed Bandit Allocation Indices by Gittins, Glazebrook and Weber if you have it, because there explanation will be much better than mine.) I'm trying ...
2
votes
0answers
282 views

Route planning in public transport application

This is a cross-post of this StackOverflow question, (I'm not aware of linking questions between StackExchange sites). You can ignore the part about programming. I'm making a journey planner (or a ...