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
0answers
18 views

Selecting objects to maximize value while under multiple constraints

I think it will be best to explain the problem first and then explain what I am thinking: I have a dataset similar to the following: ...
0
votes
0answers
21 views

PAN card verification problem [closed]

Given a paragraph P of words which contain some PAN card Numbers. Count the number of distinct valid PAN card numbers in P. A valid PAN card number is a 10 length alphanumeric word of the form: "...
0
votes
0answers
23 views

Longest common substring [on hold]

What does each cell of dp table in case of" longest common substring" denote? I am a bit confused. consider the strings X ="geek" and Y ="ge" When we construct the dp table for this ( string X is ...
1
vote
0answers
15 views

How to approach backtracking when using immutable types (Python)? [on hold]

In Python when we are building a recursive algorithm that uses backtracking a mutable type such as a list is great to use. It can be modified at each call in our recursion tree, then returned back to ...
1
vote
0answers
33 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. ...
2
votes
2answers
85 views

How can we find a palindrome within a string?

The problem requires us to find the substring within a string which happens to be a palindrome. Multiple palindromes are also allowed. For example, in "LODHIHDAK" "DHIHD" is a palindrome. Comparing ...
1
vote
1answer
38 views

Winning strategy using Dynamic Programing

Let $G=(V,E)$ be a DAG and let $v_0\in V$. Alice and Bob are playing a game in which every player has his own turn and Bob is starting. In every turn $i$, the player is picking an edge $e=(v_i,x)$, ...
0
votes
1answer
35 views

Count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum

count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum. This is my recursive algorithm, what is wrong here?: ...
1
vote
1answer
72 views

Given price and number of pages of each book, What is the maximum number of pages you can buy?

You are in a book shop which sells n different books. You know the price and number of pages of each book. You have decided that the total price of your purchases will be at most x. What is the ...
1
vote
1answer
47 views

How to find Maximum perimeter of rectangle in a grid with obstacles? (Dynamic Programming)

Can someone tell me what am I doing wrong? Problem: https://codeforces.com/contest/22/problem/B Editorial: https://codeforces.com/blog/entry/507 ( I followed the DP solution O((n*m)^2) ) Eg: ...
2
votes
3answers
73 views

Selecting items from two arrays without duplicate indices to get maximum sum

Given two arrays both of length n, you have to choose exactly k values from the array 1 and n-k values from the other array, such that the sum of these values is maximum, with constraint that if you ...
1
vote
0answers
22 views

Determining the DP subproblem given a problem

I'm reviewing DP and I was wondering the intuition behind determining the subproblems for some DP problems. For example, consider 2 similar problems. Given a set of 1, 2, and 3 steps you can take, ...
0
votes
0answers
28 views

count all possible paths of length n in an undirected graph with use of dynamic programming [duplicate]

Given is an infinitely large grid graph. Use dynamic programming to calculate the number of possible paths of a given length n from a given start node, so that fjor every path applies: a) no vertex ...
0
votes
1answer
27 views

How to solve this job scheduling programming problem?

I am trying to solve this question. The question is a variation of job scheduling. There are n processes given to you with their execution time Ti and individual ...
2
votes
2answers
116 views

Split array into contiguous subarrays of approximately same sums

My question is similar to this splitting question, but my objective function is different. Looking for an algorithm to split array of $n$ positive (integer) numbers into $N$ contiguous non-empty ...
0
votes
0answers
22 views

What does 'recursion with no explicit stages' mean in relation to dynamic programming?

I have the following excerpt from one of my assignments, essentially asking me to build on a previous formulation. However, while I can think of improvements, I have no idea if they fit the 'no ...
1
vote
1answer
29 views

Shrinking Item 0-1 Knapsack problem

I have encountered a variant of the knapsack problem with shrinking items. Effectively, it is a 0-1 knapsack problem where the initial weight of each item is $W(n)+V(n)$ and their value is $V(N)$, ...
3
votes
2answers
48 views

Maximize number of museums visited in a day

Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day. Suppose that no time is needed in ...
0
votes
0answers
36 views

Job scheduling with minimum makespan

You are given n jobs, m workstations and an n × m two-dimensional task matrix T of the time each job will spend at each workstation. Each job becomes available at a specified time and may be processed ...
1
vote
1answer
28 views

Number of ways of tiling a 3*N board with 2*1 dominoes problem

I came across this problem, Tiling with Dominoes and initially I faced difficulty in understanding the logic behind recurrence relation, but after reading it from here , I understood it. But I had a ...
3
votes
1answer
60 views

Reductions between LIS and LCS

Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls ...
4
votes
1answer
64 views

Calculating all products of $n-1$ factors when given $n$ factors

Let's assume we have an operator $$ \times: E^2\to E$$ of which we merely know that it is associative. Let's say a multiplication $e\times f$ always takes up a time of $M$ for all $e, f\in E$. We're ...
1
vote
3answers
90 views

Do all recursive problems have optimal substructure?

I am reading about dynamic programming and I understand the overlapping subproblem requirement but not sure why optimal substructure is explicitly stated. Are there problems that can be solved ...
4
votes
4answers
264 views

Algorithms for 2-colouring a 2 x N matrix

Our task is to color a given $2 \times N$ matrix with two colours red (R) and blue (B) such that no two adjacent cells are blue. For red, there are no restrictions. An example of all possible ...
0
votes
0answers
15 views

Why does the knapsack dynamic programming solution has runtime of O(nW)? [duplicate]

Can you please help me analyse the runtime of the knapsack dynamic programming (which i have seen somewhere is O(nW))? This is the algorithm i an using: Define M[i,s] to be the maximum value that ...
0
votes
1answer
45 views

Multiple choices for a single case in the recursive formula of a Dynamic Programming algorithm

I am developing a Dynamic Programming algorithm for a problem in scheduling. In the recursive formula, I have three cases: (1) $t_{i-1} = int$ (2) $t_{i-1} = app \quad \& \quad r(j) \leq p $ and (...
1
vote
1answer
66 views

Dynamic programming - maximize sum of functions subject to constraints

Let $\{f_i\}_{i=1}^{k}:[0,k]\to\mathbb{Z}$. The problem: Maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint $\sum_{i=1}^{k}x_i\le k$ I think we suppose to come up with a ...
4
votes
0answers
66 views

Maximum weight independent set in a King's graph

I would like to find a maximum weight independent set in a finite section of a King's graph. For an $m\times n$ King's graph where $n \ll m$, we can use an $O(2^{2n} m)$ bitmask dynamic programming ...
1
vote
1answer
98 views

How many ways to express N as sum of 2, 3 and 5?

I've learnt about problems about express N as sum of 2, 3, 5. For examples, if N = 7: N = 5 + 2 N = 2 + 5 N = 2 + 2 + 3 N = 2 + 3 + 2 N = 3 + 2 + 2 But most of I found on the Internet that the ...
2
votes
1answer
68 views

Given an array of size n, create a sub array with given conditions using dynamic programming

We are given an array of integers of size n, which is not necessarily sorted, and we want to create a sub array. We are allowed to do one of 3 tasks below in each level: 1. skip the number in original ...
1
vote
1answer
50 views

How to count the combinations not greater than a given volume in a knapsack problem?

You are given a certain set of items with weight wi and the volume of the bag. Case: ...
3
votes
1answer
357 views

Use dynamic programming to merge two arrays such that the number of repetitions of the same element is minimised

Let's say we have two arrays m and n containing the characters from the set a, b, c , d, e. ...
0
votes
1answer
200 views

How to divide a line of numbers into N groups such that the sums of each group are closest to their mean using dynamic programming? [duplicate]

I have M numbers arranged into a line. I need to divide the line into N groups without changing numbers order such that the sums of the numbers of each group are closest to the mean of these sums by ...
1
vote
2answers
67 views

Given matrix, count paths visiting each number exactly once

We are given matrix of size at most $21$ by $21$, each number of the matrix is either $-1$, which means empty element, or integer between $1$ and $21$. Each integer may occure several more times in ...
2
votes
1answer
83 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...
0
votes
0answers
20 views

Analysis Or Review Of Article “Table Design In Dynamic Programming”

I was wondering if anyone could point to some sort of review to this paper "Table Design In Dynamic Programming" by Peter Steffen and Robert Giegerich? https://dl.acm.org/citation.cfm?id=1182768 Has ...
0
votes
0answers
69 views

Implementing a job-scheduling problem with multiple dependencies and variable tasks (time frames) using dynamic programming

I'm writing a "Chores Scheduler" in Python. It has to be implemented using dynamic programming and has to take in two types of chores, as below: Regular chores with a start time and end time (a real-...
0
votes
2answers
113 views

How to solve a DP problem that minimizes a sum of cubic powers?

I am trying to practice some coding problems and I came upon this problem: As electricity prices are soaring, there must be a way to reduce wastage by increasing the utilization of heavy duty ...
0
votes
1answer
39 views

invariant of bin packing

We are given an array of integers and a number K. We need to pack these integers into bins. The condition is that we have to use exactly K number of bins and each bin should have equal capacity. We ...
0
votes
1answer
47 views

Hitting probability of random walk within given number of steps

Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates. What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially? We can ...
5
votes
1answer
59 views

Word Problem over Finite Groupoids

I'm struggling with an interesting problem from a chapter about Dynamic Programming in Skienas' famous "The Algorithm Design Manual". It's listed on the following web-page under number 8-22: http://...
2
votes
0answers
100 views

Join Order Optimization

Consider the join: (σtitle=Overwatch Game)⨝ Event ⨝ rating ⨝ Player What is the optimal join order? Based on the schema on the following picture: I am suppoused (and that's what I tried) to use ...
2
votes
1answer
266 views

Finding the largest possible area covered by M rectangle under a given histogram

Finding the largest rectangular area possible in a given histogram is a well-known problem and have linear solution. I have a similar but different problem. In my problem, we have $M$ rectangles ...
1
vote
1answer
56 views

Edit Distance Algorithm (variant of longest common sub-sequence)

I'm working on a school assignment which is defined as a variant of the longest common subsequence problem and which is presented in the context of dynamic programming. The problem is defined as ...
0
votes
1answer
65 views

In which order to solve subproblems when using memoization?

I am currently trying to solve a task with memoization. I have following recursion: A (i, j) = f( A (i, j-1), A (i-1, j-1), A (i-1, j + 1) ) I am not sure in which order the sub-problems should be ...
1
vote
1answer
184 views

dynamic pseudo-code for simplified coin changing algorithm

As a homework exercise our professor presented to us a simplified version of the coin-changing problem in which we do not need to minimize the number of coins used or track the number of possible ...
0
votes
2answers
132 views

Interview Questions for Minimum Cost of Tasks

I got this problem as an interview questions and I was blank all the way, I thought it was pressure but as I try to do it now I am still blank, anyway to solve this problem, I am blank so a solution ...
2
votes
0answers
57 views

Minimum number of deleting palindromes to delete whole string

Let's say we have given array $A$ of size $n$. Our goal is to delete the whole array with minimum steps. In one step we can choose substring (consecutive elements from the string) and delete it only ...
1
vote
1answer
85 views

To check if a chain with $n$ links can be “folded” into a size at most $L$

Given a chain of $n$ links, each of length $a_1, a_2,..a_n$, where each $a_i$ is a positive integer. $L$ defines the length of the "folded" chain. More formally, we want to decide whether there exists ...
0
votes
0answers
25 views

Two-dimensional Range Minimum Query under a constraint

So, I have trouble understanding and solving the following question: You are given a 2D array. Design an algorithm that, given two coordinates (each with two indexes ofc), returns the minimum in the ...