Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
765
questions
2
votes
1answer
145 views
Finding all partitions of a grid into k connected components
I am working on floor planing on small orthogonal grids. I want to partition a given $m \times n$ grid into $k$ (where $k \leq nm$, but usually $k \ll nm$) connected components in all possible ways so ...
-2
votes
1answer
2k views
How to calculate the minimum price required to buy all the stones?
I have shared the question above. My current algorithm does the calculation in O((n^4)*(2^n)).
Can someone please help me out to solve this faster?
0
votes
0answers
71 views
Get the maximum sum of n items below a threshold
Consider a modified Knapsack Problem where:
The number of items to be included is fixed.
The value of each item is equal to its weight.
Therefore, given a set of numbers, a threshold and the number ...
1
vote
1answer
399 views
How do I calculate the time complexity of this memoized algorithm?
The problem is: count all increasing subsequence of s.
...
1
vote
1answer
90 views
How to solve a problem about balancing parentheses with smileys?
I'm new to dynamic programming and find a problem about balancing parentheses and smileys ":)" and "(:" at HackerRank, which is impossible to do.
I've been trying to solve it by 3 ...
0
votes
1answer
34 views
What is the difference between these two Edit Distance Algorithm
Edit Distance is very well known problem in computer science. Came up with following algorithm after reading through CLRS but it doesn't work. Check the working algorithm below, I couldn't find why ...
0
votes
1answer
63 views
Knapsack problem with a constraint
I am familiar with 0/1 knapsack problem.
But if the following constraint is imposed... how do I solve the question?
If you choose some item 'U' you won't be able to choose another item 'V'.
For ...
0
votes
1answer
20 views
complexity of dividing set of number with constraints
I've been thinking about a division problem for groups that I haven't found a dynamic programming solution and I'm trying to analyze the complexity of the problem.
There is a set of $n$ positive ...
0
votes
1answer
96 views
Contiguous Subarray Max
I'm trying to solve the contiguous subarray problem on CodeSignal & I came up with the following solution which is based off of Kadane's Algorithm. My implementation passed the given test data set ...
0
votes
1answer
57 views
Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items
Assume for the regular knapsack problem we have additional information - maximal weight of every item - lets denote it as P. Using this information, I want to solve the problem using dynamic ...
0
votes
1answer
29 views
Issue with Campaign problem to find distinct valid campaigns
Question:
An email campaign has a sequence of email messages
where each email message belongs to one of two categories:
transactional (and/or) marketing.
Given the campaign size n and the gap length ...
1
vote
1answer
194 views
Minimum cost of “signal” cover in a tree with DP
I'm given a (not necessarily binary) tree. Now every node can have a signal with range $i$, reaching all nodes being at most $i$ edges away. The cost of a signal is determined by a function $f(n, i)$ ...
0
votes
1answer
45 views
Minimization of amount in the change coins problem using the dynamic programing approach
I'm learning the dynamic programming approach to solve the coins change problem, I don't understand the substitution part
Given: amount=9, coins = [6,5,1],
the ...
3
votes
1answer
117 views
Dynamic Programming - Thief Variation Probem
I've encountered a Dynamic Programming problem which is a variation of the thief one.
Say you are a thief and you are given a number of houses in a row you should rob :
$$House_1,House_2 \dots ...
0
votes
1answer
96 views
Can the algorithm be optimized?
I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach ...
3
votes
0answers
413 views
Facility location on a tree
Question:
Given a tree representing a neighbourhood where each node is a house.
Assign an antenna to each node such that the whole tree is covered.
An antenna of strength 0 can only ...
1
vote
1answer
102 views
Space optimised versions of Coin Change and Knapsack Problems in Dynamic Programming
I have recently been focussing on DP formulation and space optimization in dynamic programming of some problems.
I have gone through the standard questions such as 0-1 Knapsack and Coin Change ...
0
votes
1answer
59 views
Most cost effective way to traverse a set path
I have a set path of $N$ destinations to be visited in order, knowing the distance $D_i$ between each one of them. I can traverse one node $i$ with the cost of $D_i \times r$ or traverse any $5$ nodes ...
11
votes
6answers
1k views
Find the number using binary search against one possible lie
We all know this classic problem, "there is some hidden number and you have to interactively guess it.", which could be solved using binary search when we know that maximum number that we can guess.
...
2
votes
2answers
124 views
Is there a dynamic programming solution to the student allocation problem?
The student project allocation problem I am trying to solve goes as follows.
There is a set $S$ of students and $P$ of projects such that $|S| \leq |P|$.
Each student makes a top $3$ of their ...
-1
votes
1answer
2k views
Maximum sum path in a matrix
Given a square matrix of size N X N (1 <= N <= 1000) containing positive and negative integers with absolute value not larger than 1000, we need to compute the greatest sum achievable
by walking ...
0
votes
1answer
227 views
Asymptotic complexity of Combination sum problem vs Coin change problem
I've been looking at the following combination sum problem:
...
1
vote
1answer
76 views
Longest Common subsequence theorem in CLRS
In CLRS in the dynamic programming chapter, there is a theorem about the longest common subsequence prefix that states the following:
Theorem Let the $X=(x_1,x_2,\dots,x_m)$ and $Y=(y_1,y_2,\dots,...
-2
votes
1answer
76 views
Wall Climbing Dynamic program
How do i solve this? I am not sure where to start.
I am trying to define a Optimum solution which i can use to create a dynamic program. I am not sure what the characteristics of the optimum should be....
2
votes
1answer
92 views
Dynamic Programming, Counting Independent Sets
My first thought is to make OPT(i, j), where i is n, and j is some condition on the column. But
my experience with DP is from knapsack and weighted interval scheduling, but I'm unsure of how to ...
-1
votes
1answer
107 views
Max sum non adjacent and k size subsequence
You are given a number n, representing the count of elements.
2. You are given n numbers, representing n elements.
3. You are given an integer k.
3. You are required to find the maximum sum of a ...
1
vote
1answer
111 views
Longest Even-Length Palindromic Subsequence (with distinct adjacent characters except for the center 2 letters)
You are given a string S containing lowercase English characters. You need to find the length of the largest subsequence of S that satisfies the following pattern:
X1,X2,X3...Xn,Xn,...X3,X2,X1
where ...
1
vote
1answer
50 views
Problem related to set partitioning
Let $A_j=\{(a^i_j,b^i_j)~:~ 0 \leq i \leq n,\text{and } a^i_j,b^i_j \in \mathbb{Z}^+\}$
Given sets $A_1,\ldots, A_{p}$ and a positive integer $k$, the problem is to check whether there exists one ...
2
votes
1answer
80 views
Algorithm to partition students in two groups maintaining brotherhood (related to COVID19 pandemic)
I need to find an algorithm for the following problem. Any idea to which kind of algorithm to look for as starting point is welcomed. Should I look for a graph algorithm? Combinatorial problem? ...
0
votes
1answer
154 views
Maximum value of $\{ i \land n \mid a \leq i \leq b \}$
I was doing problems in "Leetcode" and found a problem that I could not solve.
Given a non-negative number $n$ and two non-negative numbers $a$ and $b$, consider every number $i$ such that $a \leq i \...
0
votes
1answer
155 views
Minimum steps to sort array [closed]
Consider you have a permutation of $1$ to $n$ in an array $array$. Now select three distinct indices $i$,$j$,$k$, there is no need to be sorted. Let $array_i$, $array_j$ and $array_k$ be the values ...
2
votes
1answer
62 views
House painting problem where the house row is split and converged back
I am trying to solve a house painting problem: There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You ...
0
votes
0answers
110 views
How to trace Subset from Boolean DP table in the Subset Sum Problem
I have seen that the Subset Sum Problem can be solved using Dynamic programming and we should look up the Last row's last column to return the result.
My questions are.
How did someone conclude that ...
1
vote
1answer
48 views
Monotonic queues recurrence relation
I'm looking at the following explanation of monotonic queues and their applications in problem solving.
Monotonic Queue Summary
I have a reasonable understanding of this data structure and the ...
1
vote
0answers
41 views
Partially defined boolean function
Consider a Boolean function $f(x_{1}, x_{2}, \dots, x_{n})$. The value of $f$ is defined on some set of inputs, and some inputs are undefined (let us label undefined value with $?$). It is possible to ...
0
votes
1answer
52 views
How do I design a DP algorithm to count the minimum amount of continuous palindromic subsequences in sequence?
Taking a sequence, I am looking to calculate the minimum amount of continuous palindromic subsequences to build up such a sequence. I believe the best way is using a recursive DP algorithm.
I am ...
0
votes
1answer
24 views
Find the k-th member of the recursive sequence
I have a recursive sequence: $a_n = 5a_{n - 1} + 2a_{n-2} + 3$, for $n > 1$. And I could return $k-th$ member in $O(\log{k})$ of sequence i.e. $a_k$.
I know how to get the formula of the $k-th$ ...
0
votes
1answer
53 views
Why is a Knapsack problem not an LP problem?
We know that LP can solve optimization problems that have linear constraints and linear objective functions.
A knapsack problem can be formulated into a linear objective function (because it is just ...
0
votes
0answers
86 views
Dynamic programming algorithm to merge two lists maintaining relative order and minimizing cost between elements
So I have a problem in which I have two lists of physical exercises (routines) and I want to merge them such that the merged list maintains the relative order of the previous lists, so for example, if ...
1
vote
1answer
54 views
Using Subset Sum algorithm $O(n)$ times to find the subset
Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given ...
0
votes
3answers
128 views
Minimum number of ways to write a string
Consider the following question
There are K magical pens (numbered 1 through K). You are given strings P1,P2,…,PK (each of which consists of characters from 'a', 'b', …, 't') ; for each valid i, the ...
0
votes
0answers
55 views
Multiple Optimal Solutions in Dynamic Programming
In 2-D dynamic programming problems like Edit Distance and binary knapsack, there can be multiple optimal solutions. By tracing back from the last element in the matrix one could trace out all the ...
0
votes
0answers
45 views
Matrix chain multiplication using dynamic programming
Consider we need to solve the Matrix chain multiplication using dynamic programming for this problem :
The table for min. cost is shown below :
Edit : Reference https://www.radford.edu/~nokie/...
1
vote
1answer
96 views
interval scheduling variant: 1 machine with 2 tasks need to complete only
I am looking for an optimal solution of an interval scheduling variant.
Basically, given n tasks with the start time Si and end time Ei, select EXACTLY two tasks whose execution periods are maximum ...
0
votes
1answer
52 views
Simple pathes in an acyclic graph
How to answer on many requests by type:
Count amount simple paths passing through chosen edge in an acyclic undirected graph using dynamic programming?
0
votes
1answer
101 views
Minimal number of changes to make string into concatenation of $k$ palindromes
The following question is taken from leetcode: 1278. Palindrome Partitioning III
You are given a string $s$ containing lowercase letters and an integer $k$. You need to:
First, change some ...
1
vote
1answer
52 views
Longest subarray with at most two different values - Runtime complexity for a DP solution
Consider the problem of finding, for a given input array, the longest subarray with at most two different values.
For example:
...
1
vote
1answer
77 views
Partition the indices of 2d array to minimize sum of sub-matrices
Given an $n\times n$ Matrix $M$, and the indices $[{1,2,3,4,...,n}]$ are divided into several intervals : $[1,x_1],[x_1,x_2],...[x_k,n]$, which further extract several squared sub-matrices along the $...
0
votes
1answer
79 views
Finding total valid strings of length N that could be formed using characters A,B and C which satisfies given criteria
You have to find out the number of good strings of length N characters in size which you can make using characters A B and C.
A string is a good String if it satisfies the following three criteria:
...
1
vote
1answer
82 views
Number of sequnces with given value
Consider a valid string with bitwise operations (AND, OR, XOR), and also placeholders $X$, where each $X$ stands for an arbitrary number from $\{0,1\}$. There are $n$ many $X$s, so there are $2^n$ ...
