Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
595
questions
3
votes
1answer
55 views
How can you compute the expected edit distance in $O(2^{3n/2})$ time?
In a coding challenge an answer claimed to be able to compute the expected edit distance between two binary strings of length $n$ in $O(2^{3n/2})$ edit distance calculations by dynamic programming. A ...
-1
votes
0answers
16 views
Whats the name of the library for dynamically choosing a sorting algorithm?
I got tired of googling for it, IIRC Facebook or Google created a library that explored the data before deciding which algorithm to use, I thought it was called F15 or something. it made some insights ...
3
votes
2answers
106 views
Thought process to solve tree based Dynamic Programming problems
I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems ...
-1
votes
0answers
36 views
A deck drawing problem
Given two decks of cards (ammount of cards in each deck is n) where each card holds a character, removing a card from the top of one of the decks counts as one action. If both decks show the same ...
0
votes
1answer
57 views
Dynamic programming
Got a question and can't manage to find an answer, so help will be appreciated.
I should design an algorithm, using dinamic programming, that gets as an input a matrix, named A, with n rows and k ...
1
vote
1answer
37 views
Maximum number of similar groups of a given size that can be made from a given array
I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by $B$ and the size of the group be $A$.
I need to find the maximum number of groups with the ...
4
votes
1answer
243 views
Find if there is matrix that satisfying the following conditions
Given a matrix $A_{n\times n} = \{a_{ij}\}$ such that $a_{ij}$ is a non-negative number and given 2 vectors $(r_1,r_2,...,r_n)$ , $(c_1,c_2,...,c_n)$ such that $r_i,c_i\in \mathbb{Z}$ define an ...
0
votes
0answers
33 views
What are some variants of the rod cutting problem?
I am looking at the possible implementations for solving the rod cutting problem (CLRS). Do you know of any variants of this problem and their use in industry?
0
votes
0answers
39 views
A variant of the knapsack problem
Consider the following variant for the knapsack problem: the input are disjoint sets of items $ T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
1
vote
2answers
736 views
min vertex cover to access k edges in a tree
I need to find the minimum number out of $N$ vertices on a tree with $N-1$ edges, so that at least $K$ edges of that tree are connected to these vertices.
For example, if $N=9$ and $K=6$ and we have ...
3
votes
1answer
81 views
Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems
I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences.
The first problem I solved was longest palindromic substring ...
0
votes
0answers
29 views
Schedule a Seminar in Minimum Time
There are t1, t2, t3,.....,tn topics which are to be scheduled in a building with c1,c2,c3,....ck halls. Members have already registered there interests on the topics, and they have liberty to choose ...
3
votes
1answer
94 views
Given n sorted arrays with size k select one element from every array such that the sum of the elements is minimum and the sum of their indices is k+1
So if $k = 3$ and $n = 2$ and we select the element $a_1[3]$ of the first array then we have to select $a_2[1]$ from the second array. If we select the element $a_1[2]$ then also $a_2[2]$ must be ...
2
votes
1answer
36 views
(Leetcode) Combinatorial Sum - How to generate solution set from number of solution sets?
The following question is taken from Leetcode entitled 'Combination Sum'
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique ...
1
vote
1answer
128 views
Counting number of paths between two vertices in a DAG
I need an algorithm that computes the number of paths between two nodes in a DAG (Directed acyclic graph) I need a dynamic porgramming solution if possible.
1
vote
0answers
51 views
Optimal ordering - Dynamic programming on subsets
We have a set T of n elements and m subsets $R_i \subset T i = 1,...,m$.
The $S_i$ are not assumed to be different. We also define an ordering of T, a one-to-one mapping $\pi$ of $T$ onto the set of ...
1
vote
0answers
19 views
Dynamic programming for subsequence metric
Let $a = a_1, \ldots, a_n, b = b_1, \ldots, b_m$ be sequences of positive integers and for any respective subsequence of length $k$, we consider $\sum_{i=1}^k (a_{x_{i}}-b_{y_{i}})^2$. Given a bound $...
1
vote
1answer
73 views
longest palindromic subsequence / substring and dynamic programming
The longest palindromic subsequence problem can be solved using dynamic programming because it is recursive and has overlapping subproblems, as described in https://www.geeksforgeeks.org/longest-...
0
votes
2answers
46 views
Why this greedy algorithm fails in rod cutting problem?
Recall the rod cutting problem.
Given a rod of length $n$ inches and a table of prices $p_{i}$ for $i=1,2,3,4,\,.\,.\,.$ determine the maximum revenue $r_n$ obtainable by cutting up the rod and ...
0
votes
0answers
86 views
Minimizing the distance from a set of nodes in a tree
We have a binary tree with n nodes and a number k which signifies the number of nodes that we put on a set. What is the optimal algorithm to select a set consisting of k nodes, that minimizes the ...
2
votes
1answer
31 views
How does a dual core microprocessors run so many programs?
I have a laptop with Intel dual core and it runs, the OS windows, and many application from Opera, age of empires, word, excel etc open at once just fine. If it only has 2 cores, how can so many ...
0
votes
0answers
36 views
Egg dropping problem binomial coefficient recursive solution
I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors)
In the binomial coefficient solution we construct a function $f(x,n)$, ...
4
votes
0answers
65 views
Assign n people to m rooms of different sizes, such that noone is alone
I'm looking for an efficient way to assign n people to m rooms in a very specific way.
INPUT:
The program receives two sets of people (set of males and set of females), as well as a set of available ...
1
vote
1answer
141 views
Selecting elements from two arrays to get a target sum
Let $A$ and $B$ be two arrays of size $n$ with positive integer values. Let $k$ be a given positive integer.
Design an algorithm to solve the following problem.
For each index $i$ ($1\leq i \leq n$)...
3
votes
1answer
100 views
Is dynamic programming restricted to optimization problems?
The usual criteria used to decide if a problem can be solved using dynamic programming is (1) if it has optimal sub-problems and (2) if it has overlapping sub-problems. Does the word "optimal" mean ...
5
votes
0answers
74 views
Find the 'best' longest common subsequence
I am writing a program that computes and displays diffs. I implemented Meyers algorithm that computes the LCS between 2 subsequences (seq1 and ...
2
votes
1answer
48 views
Find $n'th$ perfect number , where perfect number is a positive integer whose sum of digits is $10$
For example $46$ is a perfect number , since $4+6=10$ . If $n=1$ , answer is $19$. If $n=2$ , answer is $28$. If $n=3$ , answer is $37$ and so on .We need to make a program which takes $n$ and ...
1
vote
0answers
36 views
Weighted Activity Selection Problem with allowing shifting starting time
I have some activities with weights, and I would like to select non overlapping activities by maximizing the total weight. This is known problem and solution exists.
In my case, I am allowed to ...
1
vote
0answers
16 views
Dancing Links use in tiling problems
I'm using Knuth's Dancing Links (dlx) algorithm to solve for solutions to tiling a 2xN rectangle using 3 different pieces of one, two, or three squares. It's working correctly in its basic form but ...
0
votes
0answers
36 views
Minimum changes to obtain an alternating sequence [duplicate]
I've been studying dynamic programming lately and came across a problem that is, I believe (might be wrong, though), a modification of the classic longest alternating subsequence (LAS) problem.
But ...
-1
votes
1answer
44 views
You have K amoebas and one amoeba can divide into A,B,C amoebas after one instruction then find the minimum no. of instruction to have N amoebas
. You have developed an artificial amoeba, and you can control exactly how it divides.
Each individual amoeba can be instructed to divide into A, B, or C amoebas. That
is, if you instruct an amoeba to ...
0
votes
1answer
17 views
Determining whether a change in an memoized algorithm will improve the performance
I have an algorithm that constructs an optimal binary tree using dynamic programming. After introducing what I thought would be an optimization, the algorithm became over 2 times slover. Question: Is ...
0
votes
0answers
21 views
Dynamic programming algorithm with an O(n) performance that will give the optimal solution
I am currently learning the dynamic substructure and optimal solution for the coin change-making, and one of the questions given from my teacher is to describe an overall O(n) dynamic programming ...
2
votes
0answers
35 views
Finding a non negative combination of integers that adds up to a certain number [duplicate]
I have a set of positive numbers: ${n_1,n_2,...n_k}$ s.t. $n_1>n_2>\dots >n_k$.
I want to find an array of non-negative integers $c_1,c_2,\dots,c_k$ such that
$$n_1c_1 + n_2c_2 + \dots + ...
2
votes
1answer
38 views
Queries on knapsack
Given items with weights $w_{1}, w_{2}, \dots, w_{n}$ and queries of form $(l, r, w)$ asking for possibility to find a subset of items $w_{l}, w_{l + 1}, \dots, w_{r}$ with total weight $w$, how to ...
3
votes
0answers
119 views
Making an array increasing by modifying elements
I am trying to solve a problem on codeforces. Given an integer array $a_1,\ldots,a_n$, our goal is to find the minimal number of instructions, each of which increments or decrements a single entry, ...
1
vote
1answer
30 views
How to solve Assigment problem on SPOJ? [closed]
Problem Link - Assign .This problem is known as assignment problem.
I read few solutions Here is one and they are trying to solve it using Bit-masking and DP .I tried and thought hard to ...
2
votes
2answers
138 views
Multiple choice knapsack dynamic programming
Giving a the following:
A list of a store items $T=\{t_1, t_2,...,t_n\}$.
A list of prices of each item $P=\{p_1, p_2,...,p_n\}$.
A list of quantities of each item $Q=\{q_1, q_2,...,q_n\}$...
1
vote
1answer
50 views
Converting a greedy algorithm to a dynamic programming algorithm
Suppose I have a greedy approach to solve a certain problem. Say, I wish to solve the problem of coloring a particular graph. Now, my naive approach would be:
First, find a maximum indpendent set of ...
-1
votes
1answer
76 views
How to compute total number of subsequences of length k from a word of length N?
A subsequence of a word is obtained by dropping some letters from it. The letters
that are dropped need not be consecutive. For instance, ba, bna and banaa are all
subsequences of the word banana.
We ...
0
votes
0answers
22 views
Dynamic programming solution to Matrix chain multplication order - time complexity
I am unable to understand why the dynamic programming solution to Matrix chain multiplication order problem is O(n^3). Can someone please help understand the reasoning?
To me, it looks like the ...
2
votes
2answers
35 views
Minimum words in a string given a dictionary
The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words ...
2
votes
1answer
43 views
Grokking pseudo-code for solution to gas station problem
I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill ...
3
votes
0answers
43 views
Forbidden Sequence Dynamic Programming
Given a finite set $\Omega$, I have the following problem. Say there is a list of forbidden subsequences $F \subset \Omega \cup \Omega^2 \cup \Omega^3 \dots \Omega^\infty$, while we do not know the ...
1
vote
0answers
37 views
How does the asterisk (*) work in the wildcard matching problem?
This is a wildcard matching problem. Given a pattern P containing letters and character * that can match an arbitrary string of characters (including an empty string), my task is to write a polynomial-...
1
vote
2answers
44 views
Find the minimal tank capacity to be able to travel from any city to any other
There are $n$ cities in the country. The car can go from any city $u$ to city $v$, On this road it spends $w_{u,v} > 0$ fuel. At the same $w_{u,v}$ can differ from $w_{v, u}$. The task is to find ...
2
votes
0answers
20 views
Seeking an algorithm for finding the partition of data on an interval that maximizes the minimum fitness among the blocks
In the paper "An algorithm for optimal partitioning of data on an interval" (link) the authors describe an algorithm for partitioning data on an interval to maximize a fitness function. The fitness ...
0
votes
0answers
60 views
How to solve this dynamic programming puzzle on matrix?
We are given 4 integers N,M ,Q and Z.
Initially,the matrix has all zeroes in it.
We have to perform Q operations on the matrix.
In each operation, any cell of the matrix can be selected(same cell ...
0
votes
2answers
116 views
number of permutation with k inversions
We are given two numbers N and K.
N <= 10^9.
K<=min{1000,(N*(N-1))/2}
We need to find numbers of permutations of ( 1 to N ) such that inversions are exactly K.
If N was <= 10^3. It would ...
3
votes
4answers
99 views
Divide $n$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people
Divide $n$ gifts of different values among three people so as to minimize the difference in the total cost of the gifts for the most lucky and the most unlucky persons.
The total value of $n$ gifts ...
