Questions tagged [dynamic-programming]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
36 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, m_D)...
1
vote
2answers
669 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
643 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 ...
3
votes
0answers
3k views

Route planning in public transport application [closed]

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
4k 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 "...
5
votes
1answer
384 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
778 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
489 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
121 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
494 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 ...
3
votes
1answer
5k 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 $O(nV^...
4
votes
1answer
308 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
3
votes
1answer
194 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 ...
6
votes
1answer
13k 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
703 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
188 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 ...
2
votes
1answer
2k views

Upper Bound on Runtime of Memoized DP Algorithms

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 functions....
1
vote
2answers
925 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 2^2+3^2 ...
-4
votes
1answer
259 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 time ...
4
votes
3answers
4k 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 ...
1
vote
2answers
495 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
255 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
1k 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
520 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 ...
1
vote
1answer
914 views

String similarity problem

We are given two strings $x=x_1,x_2,x_3,\ldots,x_m$ and $y=y_1,y_2,y_3,\ldots,y_n$ over some finite alphabet. We consider the problem of converting $x$ to $y$. Using the following operations: 1....
4
votes
2answers
968 views

Fuzzy string matching algorithm with allowed events?

I want to be able to locate a substring in a string allowing for a specified number of mismatches, insertions and deletions - and at the same time know how many mismatches, insertions and deletions ...
1
vote
1answer
219 views

Minimum cost subset of sensors covering targets

I have a dynamic programming problem: If I have a set of sensors covering targets (a target might be covered by mutiple sensors) how can I find the minimum cost subset of sensors covering all ...
1
vote
0answers
411 views

Recursive relation help for dynamic programming 2D plane algorithm

Consider a straight highway in the plane which can be modelled by a horizontal strip in the plane. A finite set T of targets are located on the highway, and a finite set S of wireless sensors are ...
8
votes
0answers
609 views

Chained operations on sequences with two operators

Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation? Can we learn from matrix chain multiplication? A generalization of matrix chain ...
3
votes
0answers
626 views

Best a-little-advanced examples of dynamic programming [closed]

I was offered by a professor to give some tutoring in his course of Algorithm Design, based on Kleinberg and Tardos' book. He suggested me to prepare two exercise on dynamic programming, one exercise ...
0
votes
2answers
4k views

Dynamic programming: Knapsack with repetition, Find the number of redundant machines

I have just started to learn Dynamic Programming, and so far I have studied the few basic concepts; longest common subsequent problem, edit distance problem and the knapsack problem. I have attempted ...
1
vote
1answer
1k views

Memoized Palindrome Subsequence

I am trying to find the maximum palindrome sub-sequence and after going through some tutorials, I came up with a memoized version.But I am not sure about the runtime.I want to know if the following ...
7
votes
2answers
869 views

Dynamic programming algorithms with log in the run-time

Most of the classic examples of dynamic programming algorithms have run-times such as $n$ or $n^2$. Are there any natural examples with a $O(n \log n)$ run-time?
7
votes
1answer
2k views

Levenstein distance and dynamic time warp

I am not sure how to draw parallel between the Wagner–Fischer algorithm and dtw algo. In both case we want to find the distance of each index combination (i,j). In Wagner–Fischer, we initiate the ...
3
votes
1answer
5k views

Inventory planning problem solved through dynamic programming

I am working on problem (15-11) Inventory planning from Introduction to Algorithms (CLRS, 3rd Ed). 15-11: Inventory Planning, p.411 The Rinky Dink Company makes machines that resurface ice ...
4
votes
1answer
817 views

Adjacent house , dynamic programming problem

I have to be honest this is a homework problem, but I just need to discuss this with some one. The problem is there is a row of n houses, with different profit e.g profit1 for house 1, it can be ...
-1
votes
1answer
424 views

Regarding the height of a recursion tree on dynamic programming

I am trying to understand dynamic programming and I am watching this mit video. If you guys could take some time out , can you refer to the slide on 41:36 . Why is the height m+n. I just don't get it ...
1
vote
1answer
1k views

How can I improve my Algorithm?

This is a problem from Interview Street in Dynamic Programming section. https://www.interviewstreet.com/challenges/dashboard/#problem/4f2c2e3780aeb Billboards(20 points) ADZEN is a very ...
4
votes
1answer
2k views

Maximum Schedulable Set Zero-Lateness Deadline Scheduling

This is a homework problem for my introduction to algorithms course. Recall the scheduling problem from Section 4.2 in which we sought to minimize the maximum lateness. There are $n$ jobs, each ...
-3
votes
1answer
987 views

How to do Fairy Chess problem in O(N^3)?

https://www.interviewstreet.com/challenges/dashboard/#problem/4f1c88e0dec8a Fairy Chess (35 Points) You have a $N \times N$ chess board. An $S$-leaper is a chess piece which can move from ...
2
votes
2answers
3k views

Dynamic Programming Solution for Optimal Matrix Chain Multiplication Order

I have been thinking about why the dynamic programming approach to finding the optimal matrix chain order is better than a brute force approach that finds the optimal order by exploring all nested ...
3
votes
3answers
170 views

Optimize a linear recurrence

$$\begin{align*} T[1] &= 1 \\ T[2] &= 2 \\ T[i] &= T[i-1] + T[i-3] + T[i-4] & \text{for \(i \gt 2\)} \\ \end{align*}$$ I have to calculate $T[N]$, but $N$ is too big ($\approx ...
3
votes
2answers
2k views

Dynamic programming table for finding similar substrings is too large

Substring Diff Given two strings of length $n$, $P = p_1\dots p_n$ and $Q = q_1 \dots q_n$, we define $M(i, j, L)$ as the number of mismatches between $p_i \dots p_{i+L-1}$ and $q_j \dots q_{j+L-1}...
11
votes
2answers
4k views

Dynamic programming with large number of subproblems

Dynamic programming with large number of subproblems. So I'm trying to solve this problem from Interview Street: Grid Walking (Score 50 points) You are situated in an $N$-dimensional grid at ...
4
votes
2answers
692 views

Problem contest with matrix and DP

I found this problem while I was reading an ACM problem and it is about dynamic programming. The problem says that you have a square matrix $n\times n$ filled with 1's or 0's, like this: $$\begin{...
10
votes
1answer
713 views

Micro-optimisation for edit distance computation: is it valid?

On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus: ...
8
votes
2answers
242 views

Maximum number of points that two paths can reach

Suppose we are given a list of $n$ points, whose $x$ and $y$ coordinates are all non-negative. Suppose also that there are no duplicate points. We can only go from point $(x_i, y_i)$ to point $(x_j, ...
4
votes
2answers
4k views

Efficiently calculating minimum edit distance of a smaller string at each position in a larger one

Given two strings, $r$ and $s$, where $n = |r|$, $m = |s|$ and $m \ll n$, find the minimum edit distance between $s$ for each beginning position in $r$ efficiently. That is, for each suffix of $r$ ...
2
votes
2answers
1k views

How to use dynamic programming to solve this?

Here is the question: suppose we are given x cents, the amount we want to pay, and a 6-tuple (p, n, d, q, l, t) that represents respectively the number of pennies, nickels, dimes, quarters, loonies ...
13
votes
2answers
13k views

When can I use dynamic programming to reduce the time complexity of my recursive algorithm?

Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that ...

1 9 10 11 12 13