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
213 views

If P = NP, would dynamic programming be obsolete?

I know that dynamic programming is used to solve in "pseudo-polynomial time" some NP problems, like the knapsack. If P = NP, would it mean that every problem that we solve with dynamic ...
1
vote
0answers
14 views

Resources on Dynamic Programming with Indefinite Recursion

I am trying to explain the value iteration method that is used in reinforcement learning. The method is used to estimate a solution to a recursive equation like: $ Return(state_t,action_t) = Reward(...
2
votes
1answer
22 views

dynamic programming: longest palindromic subsequence, recurrence relation question

Moving from top left down the column then over to the right column, taking ideas from here: https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/ I want to restate the question at the ...
0
votes
1answer
95 views

How to derive max amount of items from DP table of Knapsack problem?

I have a little bit changed algorithm for 1-0 Knapsack problem. It calculates max count (which we can put to the knapsack) as well. I'm using it to find max subset sum which <= target sum. For ...
1
vote
0answers
25 views

Sub-matrix with minimum size of $k$ and minimum sum

We have an $n \times m$ matrix whose entries are non-negative integers and we want to find a sub-matrix whose area (number of entries) is at least $k$ such that the sum of the entries in minimal. The ...
1
vote
1answer
31 views

Dynamic programming: Maximize total value

I was trying to solve this problem using dynamic programming. We have $n$ objects in a row where each object has a value represented with a positive number. This is encoded with an array $V[1], . . . ,...
1
vote
1answer
30 views

Time Complexity of Memoized Solution

I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on ...
4
votes
0answers
60 views

Number of permutations with satisfactory triangles

We are given $N$ points($N \leq 40$), where no combination of three or more points is colinear. The values of $x$ and $y$ are bounded by [$0$,$10^4$]. The problem is to find the number of permutations(...
1
vote
1answer
29 views

Knapsack on two kinds of objects, where you cannot choose type 2 objects on their own

I had an online round at a company where I was asked this question. There are $N$ items, and you have to choose some items from them such that the total weight does not exceed $W$. Each item has three ...
2
votes
1answer
98 views

What are the exponential alternatives that are skipped in dynamic programming for longest increasing subsequence?

I am trying to wrap my head around how dynamic programming helps avoid all possibilities that are exponential after reading Chapter 8 NP-complete problems of Algorithms by Dasgupta et al. where it ...
1
vote
2answers
102 views

Longest sequence of dominoes

Given $k$, a $k$-domino is a non-ordered pair of integer values of $[\![0, k-1]\!]$, for example $\langle 0, 3\rangle$ or $\langle 1, 1\rangle$ are dominoes, the domino $\langle 3, 0\rangle$ being the ...
1
vote
0answers
46 views

0/1 Knapsack problem with minimal cost

so i have this problem where: I have to accomplish a challenge A with n quests. Each quest gives me: p points and needs t time to be done. The object is to complete the challenge A that needs M ...
1
vote
1answer
26 views

Can the House Robber problem be solved with a Sliding Window solution?

I was reading an article on how to solve sliding window problems and it said: Fast/Lagging This one is a little different, but essentially the slow pointer is simply referencing one or two indices ...
1
vote
1answer
57 views

Greedy algorithm for maintaining drugs

Given $n$ drugs such that each drug $d_i$ should maintain in interval $[c_i,h_i]$.We want to minimize number of containers to maintain medicines in compatible interval. My answer is as follows: I use ...
0
votes
0answers
49 views

Dividing a group into two groups with equal sum

Let $P = \{p_1, \dots , p_n\}$, where $p_i ∈ \{1, \dots , K\}$ is the price of the object $i$. Check if the objects can be divided equally. In other words, there are $n$ objects with each price being ...
0
votes
0answers
23 views

Dynamic Programming, lru-cache, “minimum weight of a number”

I'm struggling with the following problem: The weight of a correct arithmetic expression, consisting only of the strings 1, x, +, is defined as the number of 1s appearing in the expression. Each ...
2
votes
1answer
64 views

Sub-exponential time algorithm to compute playoff chances

There are 10 teams, Team A through Team J, playing in a triple round robin pool (each team plays thrice against each other team, for a total of a 27 games per team). After the round robin pool, the ...
0
votes
0answers
19 views

Can the two optimal subproblems of the recurence formula below be reduced to one subproblem given the assumtions stated in the description below

In CLRS (Intro to algorithms 3rd Edition) on page 362, it says eqn(1) : Lets Assume that you are given the cost of matrix multiplication for $A_{i}..A_{j}$ is $C[i,j]$ . $C[i,j]$ is the Number of ...
0
votes
0answers
43 views

Counting number of sequences summing to target

This is a problem that I have been struggling to understand in a theoretical computer science book I've been reading: We call a sequence of $n$ integers $x_1, \dots, x_n$ valid if each $x_i$ is in $\{...
0
votes
1answer
66 views

Maximize 5-independent gifts on a path

Question: Assume there are $n$ distinct gifts on the real line. Their positions are $\{x_1, ..., x_n\}$ and each of them has an individual value $p_i$. Now you can choose a subset of them such that ...
1
vote
1answer
84 views

Dynamic programming for graph splitting

I have a directed graph which has edges between every vertices $i$ and $j$ such that $i < j$ and the edge is from i->j and every vertex needs to be visited. I need to divide the graph into two ...
0
votes
2answers
14 views

Longest common subsequence solution reconstruction during DP is wrong

I've implemented longest common substring in python. I know the usual way to reconstruct the path. But, I am reading my algorithm many times, I don't understand why ...
6
votes
0answers
81 views

Scheduling tasks on a graph with assistance

This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following: Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
0
votes
1answer
20 views

Finding shortest path for DAG using dynamic programming vs topological sort?

Why is it that when I read about finding the shortest path for a DAG I usually just hear about topological sort? Why not use dynamic programming where the shortest path to a vertex is simply the ...
1
vote
1answer
24 views

Sum of products over k-permutations

Let $A$ be a matrix of size $K \times N$, $K \leq N$. Let $n_1...n_K$ denote a $K$-permutation of integers $1...N$ (understood as a unique assignment of a column to every row in the matrix). How to ...
3
votes
1answer
140 views

Find a vector of non-negative integers $b$ that minimizes $\prod_{i = 1}^{D}\left(a_i + b_i\right)$ such that the product is a multiple of $c$

I'm trying to come up an efficient algorithm that, given a list of positive integers $a = \left(a_1, \ldots, a_D\right)$ and positive integer $c$, finds a list of non-negative integers $b = (b_1, \...
1
vote
1answer
26 views

What problem is this? Largest sum produced by selecting one number at each index from n lists, with restrictions

Suppose you have an $n\times m$ 2D array consisting of each $n$ rows of $m$ real numbers. What is the sequence of indexes $i_1,i_2...i_m$ such that $\sum_{j=1}^mA[i_j, j]$ is maximized, subject to the ...
3
votes
1answer
74 views

Completing tasks on a graph

Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. The graph $G$ is complete, which means we can traverse $(i, j)$ for all $i, j \in V$. At each vertex $v \in V$, there is a task that ...
0
votes
2answers
65 views

Question concerning subset sum problem: split into 3 equal subsets

Task: Given an array $arr[a_1, a_2, \dots, a_n]$ of integers, let $A = \sum\limits _{i\in \{1, 2, \dots, n\}}a_i$. Determine whether it is possible to spit $arr[]$ into 3 subsequences of equal sum, i....
1
vote
0answers
46 views

Best algorithm/model to establish relevance between events utilizing mixed data type (Tags, Time, x_coordinate, y_coordinate)? [closed]

I'm building a relevance ranking system for incidents occurrence and prevention. My goal is to use four attributes to establish relevance: tag (About 500 tags), x_coordinate, y_coordinate and time. ...
0
votes
1answer
134 views

Possible unique paths to reach cell (0,n-1) from cell (0,0) given vector of must visited rows and allowed movement directions

I've been given a matrix path problem to solve and I need some hints / advises. You're given a $m \times n$ matrix where $m$ is number of rows and $n$ number of columns. When you're in a cell $(i,j)$ ...
1
vote
1answer
42 views

How to create a subset with a given length and mean?

I have a set of numbers $P=\{p_1,\dotsc,p_{|P|}\}$, where $|P|$ is the length of the set. I want to select a subset, $S$, from $P$ such that its mean is approximately equal to a predefined value $\...
1
vote
1answer
76 views

What is the minimum number of parts required to split the sequence S to in order to obtain sequence T?

Suppose a person has a sequence (S) consisting of integer numbers and would like to split the sequence into a number (possibly one) of continuous parts. For each part independently, I then choose any ...
1
vote
1answer
25 views

How do these additional cases fit into this Theorem about the optimal substructure of a longest common subsequence?

Theorem 15.1 (Optimal Substructure of an LCS) Theorem Let the $X=(x_1,x_2,\dots,x_m)$ and $Y=(y_1,y_2,\dots,y_n)$ be sequences, and let $Z =(z_1,z_2,\dots,z_k)$ be any LCS. If $x_m = y_n$, then $z_k ...
1
vote
1answer
24 views

Finding optimal separating value

Problem description We are given two sorted arrays of even numbers: A and B. Values of A are generally supposed to be smaller than values of B. So we are asked to find a value X where X is an odd ...
2
votes
1answer
57 views

Question on an Algorithm for Longest Increasing Subsequence

I have been reading this paper: https://arxiv.org/abs/2011.10874 This paper presented an exact randomized algorithm with update time $\tilde{O}(n^{0.8})$. I will quickly talk about the overall idea of ...
0
votes
1answer
85 views

the number of arrangements of N players around a round table, where each player can sit on one of 3 contiguous chairs

Consider the fact that each player can either sit on their desired chair or on the neighbouring chair. Two configurations are distinct if at least one person is sitting in another chair. My attempt ...
1
vote
1answer
55 views

Minimum number of swaps to make two arrays strictly increasing

I'm trying to understand the solution of the following problem (LC 801): Given two arrays, A and B, of the same nonzero length, find the minimum number of swaps (A[i] <--> B[i]) to make A and B ...
0
votes
1answer
34 views

Longest path on a full tree

Given a full tree $\ T = (V, E, w) $ I need to find the path with maximum length from root $\\ s $ to any of the leaves. I was thinking I could use some sort of BFS. Because I'm looking for maximum ...
0
votes
2answers
123 views

Find the minimum subset of a set of numbers with product divisible by a given integer

The following problem was part of a local programming contest I attended..(I solved it via the obvious Brute Force solution) I was wondering whether there was a cleaner Dynamic Programming solution. ...
1
vote
1answer
127 views

Why is backtracking a necessary step in the Maze problem?

The problem I am working on is specifically this: A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower ...
0
votes
0answers
62 views

Dynamic programming algorithm to find largest triangle in binary square matrix where elements equal “1”

I'm struck how to find DP recurrence for: You are given a binary square matrix M of size nxn. We define a (p,q, l)-triangle of M, where p >= 1, q >= 1, L >= 1, p+L >= n+1, and q+L >= n+...
0
votes
1answer
38 views

Calculate the sum of all sub-arrays with given indices

I am new to Algorithms and Competitive Coding. I have a problem as follow: For this problem, the time limit is 1 second so brute force is not a good way to solve. The only way I think must be Dynamic ...
2
votes
3answers
106 views

how does the shap algorithm work in polynomial time?

I'm trying to understand how the shap algorithm calculates in polynomial time an estimation to the feature attribution function that satisfies the shapely value attributes (specifically for tree based ...
2
votes
1answer
59 views

Matrix chain multiplication recurrence and its solution

We want to calculate $A_1 \times A_2 \times \cdots \times A_n$, where $A_i$ has dimensions $d_{i-1} \times d_i$. In the classical matrix chain multiplication problem, we wish to minimize the total ...
0
votes
0answers
36 views

0/1 Knapsack problem. How does the total weight does not exceed the limit?

I am trying to wrap my head around the knapsack problem algorithm. I understood the most of it except one tiny thing. On the left is the [val,weight] and on the ...
0
votes
2answers
138 views

Count the possible plans for nurses

I am new to Algorithms and Competitive Coding. I read an exercise paper given by my teacher as below: The director of a hospital want to schedule a working plan for a nurse in a given period of N ...
0
votes
0answers
16 views

Write recurrence for cost minimization

So I am trying to find the recurrence for this problem but I feel like it is missing something. An ice cream shop is looking to minimize their operation costs, under the given constraints: They are ...
0
votes
2answers
43 views

Two-Sum - Range Allowance Algorithm Design

🧩 What is the best way to find if there are two individual capacities that sum to a total capacity within a range of plus and minus the total capacity? Optimize for runtime over memory complexity. ...
2
votes
1answer
28 views

What is the best algorithm to find the optimal path in reducing company's real-estate footprint?

I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it. Here is the problem: A company is in ...

1
2 3 4 5
16