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
105 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 ...
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
155 views

Line-Breaking algorithm (minimum raggedness) where spaces can have width different than 1.0

The Divide & Conquer Algorithm for Line-Breaking described here is given below, both in Python and in Dart (which is similar to Java/C#). Line-breaking is also known as "line wrap", "word wrap", ...
0
votes
0answers
31 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 ...
1
vote
1answer
71 views

Optimizing the problem

I have a recurrence relation: $$f(a,b) = \begin{cases} 1 & (a,b) = (0, 0)\\ 1 & (a,b) = (a, 0)\\ 0 & (a,b) = (0, b)\\ 2a & (a,b) = (a,1)\\ f(a-1,b) + f(a-2, b-1) + f(a-1,b-1)...
2
votes
1answer
318 views

What is the optimal way to perform GCD chain operation?

Matrix chain multiplication problem:- Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. This problem is solved using dynamic programming. Similarly ...
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 \...
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 ...
0
votes
1answer
153 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
61 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
99 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
0answers
40 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
22 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
45 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
55 views

Variant of box stacking algoritm

I'm trying to solve this problem which I believe is a variant of box stacking algorithm. Problem : Suppose I have n boxes each with height h, width w, length l. Now if one box can fit inside another ...
0
votes
2answers
481 views

Doest sorting accept a dynamic programming solution?

Are there any known / efficient dynamic programming solutions to sorting? I understand of course that dynamic programming applies to scenarios where we have overlapping subproblems and optimal ...
5
votes
2answers
666 views

Can counting problems have optimal substructure?

I understand that for a problem to be solvable using dynamic programming, it needs to have the following properties: optimal substructure overlapping subproblems I stumbled upon an article which ...
0
votes
0answers
84 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 ...
0
votes
3answers
125 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
52 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/...
3
votes
2answers
511 views

Merging balls interview problem

Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks. You are given $n$ balls on the table and all the balls are rolling towards the ...
1
vote
1answer
93 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
98 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
49 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
75 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 $...
2
votes
3answers
4k views

Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T. This question is a simplification of ...
0
votes
1answer
68 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: ...
3
votes
1answer
105 views

Dynamic Program to solve an NP-complete partitioning problem

I have this problem for which I am struggling to find an efficient dynamic programming algorithm. Would be thankful for some help!! Let $A = \{ a_1, a_2, ..., a_n \}$ be a set where $a_i \in \mathbb{...
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$ ...
0
votes
1answer
216 views

Can I find all the common subsequences between 2 sequences by using dynamic programming?

I need to know if there's a dynamic programming algorithm that returns all common subsequences between 2 sequences not just the longest one. Thank you.
1
vote
1answer
40 views

Maximize rental income given a set of date intervals

Suppose you have 1 room that you want to rent out. (AirBnb style) You want to maximize profits that you will get by renting it out. For example: Given intervals: ...
0
votes
1answer
172 views

Is there a faster than O(n^2) solution for Box stacking problem?

The Box Stacking problem is as follows: You are given a set of $n$ types of rectangular 3-D boxes, where the $i^{th}$ box has height $h_i$, width $w_i$ and depth $d_i$ (all real numbers). You ...
4
votes
1answer
409 views

Is dynamic programming restricted to optimization problems?

The usual criteria used to decide if a problem can be solved using dynamic programming is (1) if it has optimal sub-problems and (2) if it has overlapping sub-problems. Does the word "optimal" mean ...
2
votes
1answer
118 views

Knapsack-like problem with profit formula

Given two sets of $N$ integers, weights and reps, that store info about some dumbbells, find out the maximum profit by taking at most $M$ dumbbells. Each dumbbell can be taken at most once. The ...
2
votes
2answers
2k views

DP recurrence relations: Coin change vs Knapsack

Take: KP recurrence relation $ max { [v + f(k-1,g-w ), f(k-1,g)] } $ if w <= g and k>0 CCP recurrence relation $ min {[1 + f(r,c-v), f(r-1,c)]} $ if v <= c and r>0 I don't ...
1
vote
1answer
51 views

Is it possible to find a supersequence of a single array?

In Jeff Erickson's Algorithms textbook, the chapter on Dynamic Programming asks you to "Describe an efficient algorithm to compute the length of the shortest oscillating supersequence of an arbitrary ...
0
votes
1answer
44 views

Implementing Dynamic Programming Solutions

I know there alot of questions on Dynamic Programming and I feel I have a handle on the theory, use the answers from sub problems to answer the current problem, without the redundancy of recursion. ...
2
votes
1answer
98 views

Dynamic programming problem

our uni is closed because of the COVID-19 and I'm trying to homelearn dynamic programming. In our algorithms book, there is the following problem: (an example problem for dynamic programming) A ...
2
votes
1answer
135 views

LaTex Text Justification badness penalty

I had been going through dynamic programming concepts and happened to read about text justification problem in which the spaces to the right of the line end are penalized with cubic times the number ...
2
votes
1answer
1k views

Min-coin change problem with limited coins

I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite ...
2
votes
1answer
47 views

Minimum moves to “stabilize” an array

We have given an array of size $N$, consisting of positive integers, and an integer $H$. We also know that an array is stable iff $|A_i - A_{i-1}| \leq H$ for each $1<i<N-1$. We can modify the ...
0
votes
0answers
42 views

Catching ball - finding the maximum number of caught balls

I'm attempting to solve the following problem: Balls are falling from the sky. We know at which location (on a straight line) will each ball drop, and we know the time (in seconds) at which ...
7
votes
1answer
302 views

Can the solution to a POMDP be found using linear programming?

It is known that Markov decision processes (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is: $$min_{V(x)} \sum_x \alpha(x)V(x)\\...
0
votes
1answer
234 views

Cover interval with minimum sum intervals - DP recursion depth problem

READ ME FIRST: I have just found the official solutions online (have been looking for them for a while, but after posting this I quickly found it), and I'm currently trying to understand it. As I can ...
0
votes
1answer
48 views

Expected number of coins

Alice and bob play a game. Bob has a well-shuffled deck of $M=4999$ white cards and $N=4999$ green cards. Each permutation of cards in the deck is equally likely. Alice has set some rules for Bob. ...
1
vote
1answer
42 views

Amount of k-partitions of a number

I'm stuck on writing an algorithm for getting the amount of distinct partitions for a number $n$ with the partition being size $k$. It's important that there isn't any repetition in the partitions. ...
1
vote
0answers
30 views

Algorithm to minimize the damage received from the monsters [duplicate]

I have been puzzled by the following question on an exam for quite a while: given a set of monsters with their health and attack damage (per second), design an algorithm that minimizes your overall ...
2
votes
2answers
735 views

Count number of pairs of elements whose product is a perfect square

Given two arrays whose elements lie between $[1,10^5]$ and the size of arrays is $[1,10^5]$, how can we find the total number of pairs of elements from these arrays such that their product is a ...

1 2 3
4
5
16