Questions tagged [dynamic-programming]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
38 views

Count subset divisible by 3

I'm trying to solve this puzzle but I get stuck. I thought about trying to use the law of total probability to solve intermediate problems with subset of size $k$ but it didn't helped me that much. Is ...
0
votes
1answer
47 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 ...
1
vote
1answer
41 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 ...
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 ...
0
votes
0answers
17 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 ...
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....
2
votes
0answers
55 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 ...
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 ...
4
votes
1answer
244 views

How to extend Bellman-Ford to solve the $k$ shortest path routing?

Browsing the wikipedia I got to this page where it is said: Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm and extend them to find more than one ...
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 ...
2
votes
1answer
57 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
198 views

longest palindromic subsequence / substring and dynamic programming

The longest palindromic subsequence problem can be solved using dynamic programming because it is recursive and has overlapping subproblems, as described in https://www.geeksforgeeks.org/longest-...
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 ...
1
vote
1answer
997 views

Printing actual solutions for the coin exchange problem

As I teach myself dynamic programming, I have learned about the coin exchange problems. Specially this site: https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ provides great insight ...
-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 ...
5
votes
2answers
129 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 ...
7
votes
3answers
2k views

Dynamic programming: speed of top down vs bottom up approaches

I have just completed a dynamic programming exercise on LeetCode (Coin Change). I tried a top down approach, but it failed for the larger inputs, whereas the bottom up approach worked for all inputs. ...
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 ...
0
votes
2answers
5k views

Dynamic programming: Knapsack with repetition, Find the number of redundant machines

I have just started to learn Dynamic Programming, and so far I have studied the few basic concepts; longest common subsequent problem, edit distance problem and the knapsack problem. I have attempted ...
2
votes
1answer
298 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...
1
vote
2answers
221 views

FInding the combination with the least number of elements from and array of integers, given an integer sum

I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm ...
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 ...
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
1answer
868 views

Prove Recursive formula (Dynamic programming) N(C,i)

I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following ...
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 ...
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 ...
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
53 views

Applying subproblem technique to permutations with grouping

I am trying to apply overlapping subproblems and dynamic programming to permutations. Say, we have a set of $n$ elements in a string. Each of these elements could be a $1$ or a $0$. Given some ...
3
votes
1answer
898 views

How can Lagrange Multipliers and Penalty Method be applied to optimize algorithms?

I have a programming assignment which I was told that is solvable with some DP algorithm. The question is a variant of LIS problem where at most $k$ exceptions (restarts) are allowed. But I know that ...
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 ...
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
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 ...
-2
votes
1answer
42 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
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
2answers
107 views

How can I solve this problem using dynamic programming?

I'm stuck in this problem and I would need some help: Given an array arr, in each step, 1, 2 or 5 units have to be incremented to all but one item of the array. ...
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 ...
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 ...
2
votes
0answers
393 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 ...
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
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 = ...
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. ...
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
90 views

Dynamic programming

Got a question and can't manage to find an answer, so help will be appreciated. I should design an algorithm, using dinamic programming, that gets as an input a matrix, named A, with n rows and k ...
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 ...

1
2 3 4 5
14