Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
687
questions
0
votes
0answers
15 views
Are there any dynamic programming algorithms that combine solutions to sub-problems in a more 'dynamic' way?
First of all, I now know that 'dynamic' has nothing to do with the dynamism of a dynamic programming algorithm. But I didn't before I studied them, and I was kind of disappointed that they all seem to ...
1
vote
1answer
28 views
Find maximal subset with interesting weight function
You are given $n$ rows of positive integers of length $k$. We define a weight function for every subset of given $n$ rows as follows - for every $i = 1, 2, \dots, k$ take the maximum value of $i$-th ...
2
votes
1answer
10 views
Policy dependent on initial state distribution in finite horizon MDPs
Consider an MDP defined as the tuple $\langle S,A,R,P,\mu,\lambda\rangle$ where $S$ is the state space, $A$ the action space, $R:S\times A\times S\to\mathbb{R}$ the reward function, $P$ the transition ...
2
votes
0answers
54 views
Speeding up the Rummikub algorithm - explanation required
Regarding this question: Rummikub algorithm.
I was reading the first part of the solution in the posted answer (specifically, when there are no jokers involved, all tiles are distinct and only four ...
0
votes
1answer
66 views
Longest common sub-sequences with a condition
A sequence is called good if it contains at least one pair of numbers which are adjacent and equal. A good sub-sequence of an array is a sub-sequence of that array which is good and has maximal length....
1
vote
1answer
22 views
Count minimum number of steps to destroy all blocks
Given a sequence of integers $A_x$ of length $n$ such that $1 \leq A_x \leq N$,in one step we can remove an element, but when we remove an element we also delete all adjacent numbers which have the ...
0
votes
1answer
51 views
Balanced sub-sequence
Consider two strings $S$ and $T$ of length $n$. Here both the strings $S$ and $T$ consists of only
( and ) that is made of ...
-3
votes
1answer
49 views
Subset sum problem with a complication
I have a sorted list of numbers. I know they can be divided into two parts. I also know the sum of those 2 parts. I want to know what these subsets are. How can i find them?
The size of my list can be ...
0
votes
1answer
31 views
Determine if there is a subset of the given set with sum divisible by a given integer
I've been given a question to solve:
Given a set of non-negative distinct integers, and a value $m$, determine if there is a subset of the given set with sum divisible by $m$.
For this question the ...
5
votes
2answers
128 views
Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2?
The title could be a little bit confusing, and it is not easy to summarize it within a sentence, therefore I will explain it in detail below. If you have any thoughts on optimizing and rephrasing the ...
1
vote
0answers
35 views
Choosing a method for algorithmic problems - is it an art or science?
I've been doing lot of programming challenges lately (such as on leetcode.com) and often find myself in a situation when I cannot pick a method for solving a problem. I stuck with questions like - ...
0
votes
2answers
41 views
Schedule Optimization With Priority and Weighted Costs
I need an algorithm to determine the best itinerary for a series of events.
Each event has a time, location, and reward. Arriving at an event in time yields the reward; too late means no reward. Each ...
0
votes
1answer
42 views
Dynamic Programming - Tiling Question
I came across the following question while practising for my final algorithms exam, but I am unsure how to get a linear time complexity for this problem. I assumed it would require checking which ...
2
votes
1answer
55 views
Probability of winning a turn-based game with a random element
I am preparing for a programming exam on probability theory and I stumbled across a question I can't solve.
Given a bag, which contains some given amount of white stones $w$ and some given amount of ...
1
vote
1answer
81 views
Minimum number of given operations in order to group letters in a string
Description
Suppose we have a string containing letters 'A', 'B', 'C', 'D', and the characters are placed in a stack. We also have an empty stack. Ultimately, we want all of the same letters to be ...
0
votes
1answer
48 views
Distribution of resources from providers to maximum number of receivers
Consider there is a city with $n$ residents who are in need of internet and there are $m$ internet providers in the city. Here in the city every resident needs internet and every resident knows what ...
1
vote
1answer
135 views
Bellman Ford Dynamic Programming
I have been learning graph algorithms, and the concept of dynamic programming is quite succinct. However, I read that Bellman Ford is a form of dynamic programming. I am not sure why since given so ...
2
votes
1answer
49 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
41 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
42 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 ...
0
votes
1answer
37 views
How do I calculate the time complexity of this memoized algorithm?
The problem is: count all increasing subsequence of s.
...
0
votes
1answer
59 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
31 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
38 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
17 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
53 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
44 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
178 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
38 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
71 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
93 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 ...
2
votes
0answers
392 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
32 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
47 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
54 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 ...
0
votes
1answer
57 views
Asymptotic complexity of Combination sum problem vs Coin change problem
I've been looking at the following combination sum problem:
...
1
vote
1answer
35 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,...
0
votes
1answer
63 views
Dynamic Program for Tree based question
You are given a tree T where every node i has weight wi ā„ 0. Design a polynomial time
algorithm to find the weight of the smallest vertex cover in T. For example, suppose in the
following picture wa = ...
-2
votes
1answer
63 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
71 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
27 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 ...
0
votes
0answers
30 views
Linear Partition problem (Dynamic Programming) in a circular array
I am practicing algorithms for the last couple of days and I came across this question, the gist of which is:
Given apples and oranges arranged in a circle indexed form 1 to n , where n is an odd ...
1
vote
1answer
52 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
49 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 ...
0
votes
0answers
29 views
Alternate Knapsack Implementation
I came across a question that requires an alternate implementation converse to the normal Knapsack which is based on a 0-1 logic of considering whether or not to consider an item for the optimal ...
2
votes
1answer
78 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
152 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
118 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 ...
