# Questions tagged [dynamic-programming]

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

765 questions
Filter by
Sorted by
Tagged with
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 ...
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?
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 ...
399 views

### How do I calculate the time complexity of this memoized algorithm?

The problem is: count all increasing subsequence of s. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
227 views

### Asymptotic complexity of Combination sum problem vs Coin change problem

I've been looking at the following combination sum problem: ...
76 views

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