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

learn more… | top users | synonyms

1
vote
0answers
68 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
46 views

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

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
1k 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
88 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
14 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
101 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
85 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
42 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
74 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
93 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
73 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
31 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 ...
1
vote
1answer
220 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
384 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
191 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
88 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
184 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
75 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
178 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
85 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 ...
1
vote
0answers
85 views

Recalculate max-flow after removing edge with 1 capacity [closed]

So I have some graph, and I know what it's max flow is based of the Ford-Fulkerson Algorithm. With this information, I need to know how to find a new max flow when I remove an edge of this graph with ...
4
votes
1answer
334 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
78 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
601 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
23 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
156 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
143 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 ...
0
votes
0answers
30 views

What is the optimal substructure for the following DP question [duplicate]

I have been recently teaching myself algorithm by reading this classical textbook Introduction to Algorithm 3rd by Thomas H. Cormen and others. I was encountered with this following problem and was ...
2
votes
0answers
203 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 ...
-1
votes
1answer
446 views

Dynamic Programming To calculate the combinations [closed]

This is a problem from a past contest at topcoder : Problem. Its solution is given here : Solution [Scroll Down to Penguin Emperor] I am unable to understand how the section with subheading ...
6
votes
1answer
132 views

Semi-local Levenshtein distance

If you have a long string of length $n$ and a shorter string of length $m$, what is a suitable recurrence to let you compute all $n-m+1$ Levevenshtein distances between the shorter string and all ...
1
vote
1answer
242 views

Trouble understanding this dynamic programming solution

Here is the question: I have a given tree with n nodes. The task is to find the number of subtrees of the given tree with outgoing edges to its complement less than or equal to a given number K. for ...
2
votes
1answer
159 views

Find longest common subsequence in limited space

Given three strings $x$, $y$, and $z$ over an arbitrary finite alphabet, I need to determine their longest common subsequence (LCS). Example: A longest common subsequence of ...
3
votes
2answers
87 views

MAX 10-SAT Algorithm

The MAX k-SAT problem is: “Given a set of clauses C1,…,Ck, each of length k, over a set of variables x1,…,xn, find a truth assignment that satisfies as many of the clauses as possible.” I'm ...
4
votes
1answer
199 views

Issues with using greedy algorithm (Interval scheduling variant)

I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach. I have ...
2
votes
1answer
899 views

Confusion related to time complexity of dynamic programming algorithm for knapsack problem

I have this confusion related to the time complexity of the algorithm solving the knapsack problem using dynamic programming I didn't get how the time complexity of the algorithm came out to be ...
4
votes
1answer
147 views

Find the longest subsequence of two strings

I want to know which is the best way to find the longest common subsequence of two strings
4
votes
1answer
145 views

Sorting Problem

I have come across the following problem. You have $N$ registers, numbered $1,2,\dots, N$, each of which can hold an integer value. You are given the initial values of the registers, which have the ...
0
votes
0answers
22 views

DP Recurrence Relation Finding [duplicate]

How do people find the DP Recurrence relation while solving contest problems (like in SPOJ, topcoder etc.) I have read Cormen and many other algorithms book. But they just explain only one or two of ...
2
votes
1answer
347 views

How to master Dynamic Programming? [duplicate]

I am having hard times learning Dynamic Programming. I looked around the web and found many tutorials with examples. Each time I tried to figure out how to solve a new problem before looking at the ...
0
votes
1answer
208 views

Proving correctness of the algorithm for convex polygon minimum cost triangulation

I have read many solutions for the minimum cost of triangulation problem and intuitively get the idea , however I am struggling to figure out how to prove it formally. I kind of feel that it has to be ...
3
votes
1answer
51 views

Select optimal subintervals from array

I have an input array and I have to select an indefinite number of intervals from it so that the "profit" is maximal and I have exactly T elements selected in total, where T is given. Profit means the ...
1
vote
1answer
322 views

Time Complexity Upper Bound of Memoized DP Problems

I find it fairly easy to generate an upper bound for nearly any iterative solution (e.g. look at the limits on each loop, etc.), and can oftentimes create an upper bound for normal recursive ...
1
vote
2answers
235 views

Count unhappy numbers in a large interval

An unhappy number is a number that is not happy, i.e., a number $n$ such that iterating this sum-of-squared-digits map starting with n never reaches the number 1. For example, $23\rightarrow ...
-6
votes
1answer
208 views

Maximizing profit

Problem: Given 11 numbers {N1,N2,N3,N4,N5,N6,N7,N8,N9,N10,N11} where N1:amount of profit from product A N2:amount of profit from Product B N3:amount of ...
3
votes
3answers
1k views

Finding all solutions to subset sum for integers with bounded weights

Suppose I have the set of weights $W = \{w_1,w_2,\ldots,w_{50}\}$ where each $1 \le w_i \le 60$ is an integer. I am interested in determining all subsets (not just one, and not just the number of ...
0
votes
2answers
134 views

Broken stick problem

We have a broken stick. For every part, we know it's length. Our task is to connect all parts (glue them), that we will use as small amount of glue as possible. The amount of glue need to connect ...
4
votes
1answer
175 views

Smallest string length to contain all types of beads

I read this question somewhere, and could not come up with an efficient answer. A string of some length has beads fixed on it at some given arbitrary distances from each other. There are $k$ ...
4
votes
1answer
256 views

Find maximum distance between elements given constraints on some

I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements: The element 1 is in position 1, and element N must be ...
3
votes
2answers
325 views

Modified paths Counting in a Rectangle

I was solving the following problem. But I am not able to think of an efficient algorithm for this modified version of problem. The problem statement is: We are given K Rectangles. The dimensions ...