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
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$ ...

1 2
3
4 5
16