Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
-2
votes
0answers
13 views
Range queries on million number array
I have an array of million numbers. I want to find the maximum number in range queries wherein each query I am given left and right index. What is the effective way of doing that?
3
votes
2answers
73 views
Merging balls interview problem
Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks.
You are given $n$ balls on the table and all the balls are rolling towards the ...
1
vote
1answer
27 views
Trying to understand the question(well spaced points ?) better
Let us have a sorted array of n numbers and we would like to find a well spaced set of C of them, More specifically, we want to get a subset $ S\subset T$ with |S| = C and with $min_{i,j \in S,i\ne j}...
2
votes
1answer
48 views
Lexicographically smallest down-right path in matrix
Here is the problem which I thought was simple dynamic programming, which is however not the case.
Given an $N \times M$ matrix of numbers from 1 to $NM$ (each number occurs only once), find a path ...
1
vote
1answer
40 views
Shortest path from source to all vertices, but with some wildcards
Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer).
You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated ...
1
vote
2answers
77 views
Doubt over the index value used in dynamic programming
I was going through Count All Palindromic Subsequence in a given String where I've to count all the palindromic subsequence of a given string.
After seeing the brute force(recursive solution), I went ...
2
votes
2answers
32 views
Recursion to DP Solution
There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll ...
1
vote
1answer
55 views
Maximum product of contiguous subsequence over $\mathbb{R}$
For the problem of a subsequence of maximum product with negative, zero and positive integers, I have the following working solution (inspiration from here).
Let us first show how to solve the ...
0
votes
1answer
42 views
Dynamic Programming Problem on Tree
Given a tree $T$ rooted at $1$. Each node might have more than 2 children. You want to create a tree $S$ where each node have $2$ or less children or a binary tree. For each node $u$ in $T$ which had ...
1
vote
1answer
64 views
How does dynamic programming work in this example(generating the tables )
For example, a sequence has the defined growth property: if it is a
sequence of positive integers $a_{1}, a_{2}, a_{3}....a_{n}$ and such
that:
$a_{1}=1.$
$a_{n+1} \leq$ Max$_{1\leq i \...
1
vote
0answers
31 views
Text Segmentation Problem give Word Frequencies in a Universe
Given a dictionary of words and their frequencies (how many times they appear in a universe and given a string(no spaces, punctuation, etc.). What is the best way to segment into individual words? I ...
0
votes
0answers
28 views
findining the smallest sum of squared lengths of the intervals I_{k}
Given a set S = { $x_{1}$, $x_{2}$, . . . , $x_{n}$} where $x_{i} \in Z$ . and a K and it is $Z^{+}$ . The goal is to find k intervals
$I_{1}, I_{2}, . . . , I_{k}$ so that each $x_{i}$ is in one ...
-1
votes
1answer
86 views
Algorithm : Visiting all stations in minimum time with additional constraints
I was given this question and not sure how to solve this. This is a DP minimization problem ?
Problem :
There are N stations in a certain region, numbered 1 through N.
It takes di,j minutes to ...
1
vote
1answer
32 views
Computing number of ways to make change
Given a list $C=[c_1,c_2,\dots,c_k]$ of positive integers, representing the values of $k$ varieties of coins, and a positive integer $n$, let $f(n,C)$ be the number of handfuls of coins with total ...
2
votes
1answer
132 views
Solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time
Let PARTITION-INTO-THREE-SETS be defined as following:
Input: Positive integers $a_1, ..., a_n$
Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup ...
1
vote
1answer
32 views
Finding optimal multiplication order and optimal binary tree
I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree.
Consider the following ...
0
votes
0answers
18 views
Value iteration in MDP - updating each state once per inner loop?
In value iteration algorithm we update the utility of all possible states ("for each state update its new utility").
After we've updated all states we check to see if the delta is smaller than some ...
1
vote
1answer
23 views
What Are the Ideas Behind Variations of the Coin Change Problem?
Problem: given a set of n coins of unique face values, and a value
change, find number of ways of making change for ...
1
vote
0answers
49 views
Is MCTS an appropriate method for this problem size (large action/state space)?
I'm doing a research on a finite horizon decision problem with $t=1,\dots,40$ periods. In every time step $t$, the (only) agent has to chose an action $a(t) \in A(t)$, while the agent is in state $s(t)...
1
vote
1answer
49 views
Can Dynamic programming be applied to solve problems if and only if the subproblem form a DAG?
I assume Dynamic Programming can be used only when the corresponding subproblems form a Directed Acyclic Graph, otherwise you're stuck in a loop.
Is this reasoning correct or is there more to it?
1
vote
0answers
23 views
Count paths in matrix that visit each number exactly once
Let's say we are given matrix of size $N \leq 21 \text{ by } M \leq 21$ each element of the matrix is either $-1$ or number in the interval $[0, 20]$.
We want to count the number of paths that start ...
2
votes
2answers
59 views
Technique for converting recursive algorithm to DP
I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed).
But, I'm unable to convert my recursive code to <...
2
votes
4answers
68 views
1
vote
2answers
45 views
set cover where only certain special subsets are allowed
I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
1
vote
0answers
68 views
Maximize interleaving subsequences two digit arrays/strings
Suppose I have two digit arrays, A and B as follows
A = [3,4,5,6]
B = [9,8,3]
Now, I have ...
2
votes
1answer
32 views
Max sum cyclic path of fixed length in matrix
Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves ...
1
vote
1answer
44 views
Number of contiguous subsequences summing to a given target
I could not figure out an efficient way (better than $O(n^2)$) to count the number of contiguous subsequences of an array of both positive and negative integers summing up to a given number $k$.
For ...
0
votes
0answers
20 views
Multi Knapsack each with different constraints
It seems that there's no end to knapsack variations… here's the one I bumped into (at work):
There are:
N items, each with the usual value and weight properties.
M bins, each with an upper ...
2
votes
2answers
77 views
Reduce the total internal border of a set of touching rectangles (using graphs)
I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum ...
2
votes
1answer
83 views
How to find efficiently the minimum modification to avoid close consecutive numbers?
I have an array of sorted numbers:
arr = [-0.1, 0.0, 0.5, 0.8, 1.2]
I want the difference (dist below) between consecutive ...
1
vote
1answer
80 views
What is the optimal way to solve the following optimization problem
You are given a function $F$, which can take one or more positive integer operands.
Let $L=\{a_1,a_2\ldots a_n\}$.
We need to compute the function $F(L)$ using the least number of transformations/...
11
votes
1answer
192 views
Word factorization in $O(n^2 \log n)$ time
Given two strings $S_1, S_2$, we write $S_1S_2$ for their concatenation. Given a string $S$ and integer $k\geq 1$, we write $(S)^k = SS\cdots S$ for the concatenation of $k$ copies of $S$. Now given a ...
1
vote
1answer
58 views
What is the optimal way to perform GCD chain operation?
Matrix chain multiplication problem:- Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices.
This problem is solved using dynamic programming.
Similarly
...
2
votes
0answers
23 views
What are the pros and cons of context-oriented programming (COP)?
I have started reading about COP, but can't really get a grip of it. What I understand is that you use layers to let the software dynmically adapt depending on the context, and this would result in ...
1
vote
1answer
51 views
How to minimize the average distance between pumps and cities?
There are n cities [1, 2, 3, .... n] and k available pumps. These pumps can be installed in k...
0
votes
1answer
40 views
DP recurrence relations: Coin change vs Knapsack
Take:
KP recurrence relation
$ max { [v + f(k-1,g-w ), f(k-1,g)] } $ if w <= g and k>0
CCP recurrence relation
$ min {[1 + f(r,c-v), f(r-1,c)]} $ if v <= c and r>0
I don't ...
0
votes
0answers
56 views
Intuition behind Floyd-Warshall being faster
I know the Floyd-Warshall, and I also clearly understand the proof of running time of $O(V^3)$ of F-W algorithm. However, consider this algorithm:
Let $dp[i][j][n]$ denote the shortest path from $...
0
votes
0answers
46 views
What will be an O(n) solution for this?
Suppose a given piece of work can be done at two processors. One at r and another at v. The job can run only at one processor at ...
2
votes
3answers
62 views
Algorithm to find smallest number divisible by N with sum of digits as N
Problem:
Given $N$, find the smallest number divisible by $N$ whose sum of digits is equal $N$.
For example:
$n = 1$, answer is $1$
$n = 10$, answer is $190$
There is some dynamic programming ...
1
vote
1answer
56 views
Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items
For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^*n^2)$ time ($v^*$ is the maximum value of all elements)...
0
votes
1answer
38 views
Sum of zero nim sum series
The problem is proposed here and related to this question. Given $n$ and $k$, I would like to know how to compute$$\sum_{\substack{x_0 ⊕x_1⊕\cdots⊕x_k=0\\x_i≥0,\ 0≤i≤k\\\sum\limits_{i=0}^kx_i≤n-2k}}\...
1
vote
0answers
42 views
Possible Distribution of coins
We are given a set of $n$ coins with denominations $v_1,v_2,\ldots,v_n$ and a number $x$.
The coins are to be divided between to persons, with the restriction that each person's coins must add up to ...
2
votes
0answers
61 views
Balls in Bins with Pairwise Distance
Given $n$ bins in a row (numbering from $1$ to $n$) and $2k$ balls ($n \ge 2k$), one may put all balls into bins with each bin having at most one ball (there are $\binom{n}{2k}$ configurations). ...
1
vote
1answer
46 views
Algorithm Design for Linear Programming
I am trying to complete question and would like to avoid copying answers, but I do not necessarily understand what I am doing.
I am working on the following problem:
Suppose you are consulting ...
1
vote
1answer
92 views
Gerrymandering Problem: Variant on Set Partitioning
I was recently helping a friend with homework from a dynamic programming class, and this was the question:
Given a set of
n
precincts
P1
,...
Pn
, each containing
m
votes, with <...
2
votes
0answers
39 views
Tail recursion can't work with dynamic programming programs
I am doing some exercises on dynamic programming in order to get familar with this concept.
I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
0
votes
0answers
20 views
Given graph with N nodes colored in K colors, count paths visiting each color exactly once
Let's say we have given graph of at most $N = 400$ nodes, and each node is colored in one of $K = 21$ colors. We need to count paths of length $K$, such that each node on the path is in one of the $K$ ...
2
votes
1answer
46 views
Making a profit as a high-dimensional store owner?
Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient.
Let's say that I am some business owner with a set of $...
1
vote
3answers
151 views
Dynamic Programming vs Memoization
I am having trouble to understand dynamic programming. Mainly because of its name. As far as I understand, it's just another name of memoization or any tricks utilizing memoization.
Am I ...
0
votes
1answer
118 views
Help writing a dynamic programming algorithm in English
It’s Friday night and you have $n$ parties to go to. Party $i$ has a start time $s_i$ end time $t_i$ and a value $v_i \ge 0$. Think of the value as an indicator of how excited you are about that party....
