Questions tagged [dynamic-programming]

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

Filter by
Sorted by
Tagged with
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
1answer
62 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
280 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-...
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 ...
1
vote
1answer
1k 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 ...
2
votes
1answer
341 views

Going deeper with pseudo-polynomial time algorithm for set partitioning

If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next? To illustrate this ...
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 ...
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 ...
2
votes
1answer
817 views

Gerrymandering Problem: Variant on Set Partitioning

I was recently helping a friend with homework from a dynamic programming class, and this was the question: Given a set of n precincts P1 ,... Pn , each containing m votes, with ...
2
votes
1answer
656 views

DP for Weighted Interval Scheduling: why is sorting by finish time necessary?

Problem : In the weighted interval scheduling problem, we want to find the maximum-weight subset of nonoverlapping jobs, given a set $J$ of jobs that have weights associated with them. Job $i \in J$ ...
2
votes
1answer
657 views

Print (not count) all possible path classic climbing stair problem)

I came across this classic question and found may many solution to it. for loop and DP/ reclusive + memorization. Also found a twisted version of the questions asking to print all possible path ...
4
votes
1answer
214 views

Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems

I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences. The first problem I solved was longest palindromic substring ...
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 ...
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
124 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. ...
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. ...
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
403 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...
1
vote
2answers
318 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 ...
1
vote
1answer
128 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+...
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
137 views

Minimizing the distance from a set of nodes in a tree

We have a binary tree with n nodes and a number k which signifies the number of nodes that we put on a set. What is the optimal algorithm to select a set consisting of k nodes, that minimizes the ...
0
votes
0answers
40 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 ...
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
vote
1answer
112 views

Minimize $f(r,X)$ over all sets $X$ using Dynamic Programming

If a set of numbers $a_1, a_2, \cdots, a_n$ $($such that each $a_i \in \mathbb{N} \cup \{0\})$ and an $r \in \mathbb{N}$ are given, find set $X = \{x_0, x_1, \cdots, x_r \ | \ x_0 = 0 < x_1 < \...
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 ...
1
vote
2answers
574 views

Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items

For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^*n^2)$ time ($v^*$ is the maximum value of all elements)...
0
votes
2answers
92 views

Two-Sum - Pre-sort Optimization Algorithm Design

🧩 Is it possible to optimize the runtime of a two-sum solution by receiving a pre-sorted input either in ascending or descending order? 🚀 Original Two-Sum Determine whether there are two items whose ...
0
votes
1answer
139 views

For dynamic programming problems, how do we know the subproblems will share subproblems?

So, a common reasoning to use dynamic programming as the website (https://www.tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm) mentions is that, we use dynamic programming when: ...
4
votes
2answers
1k views

Technique for converting recursive DP to iterative DP

I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed). But, I'm unable to convert my recursive code to <...
2
votes
0answers
63 views

Relationship between dynamic programming and reinforcement learning

I wasn't sure whether to post this here or in the ai stack exchange - please let me know if i need to move my post elsewhere) I have been learning about how dynamic programming can be used as a tool ...
1
vote
0answers
31 views

Find exact sum in path

So the question is Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move down and to ...
1
vote
1answer
81 views

Minimum sum of squared Euclidean distance between two arrays

Question: Given two sorted sequences in increasing order, $X$ and $Y$. $Y$ is of size $k$ and $X$ is of size $m$. I would like to find a subset of $X$, $i.e$, $X'$ of size $k$, and considering the ...
0
votes
1answer
63 views

approaching dynamic programing for problem

I want to find a solution to a problem that asked before. in the following question: https://stackoverflow.com/questions/43435799/path-with-the-minimum-number-of-alterations-in-graph-with-colored-...
1
vote
1answer
37 views

Does this LCS algo generate all the CS or only all the LCSs?

The Wikipedia article on LCS has an algorithm that backtracks all the LCS strings. This link redirects to the desired bulletin in the article. The C table in the backtrackAll function is pre-...
1
vote
1answer
28 views

Generating all the increasing subsequences

Given an array of integers, how can we generate all the increasing subsequnces of length of 4 ? Example: given this list l = [1, 2, 4, 5, 3, 6] The answer should ...
1
vote
2answers
97 views

Is there any algorithm for 3SAT problem that is fast and relatively easy to implement?

Here is the description for 3SAT satisfiability problem. I already know about the DPLL algorithm, but it's implementation is pretty complex. I would like some algorithm that is relatively simpler but ...
1
vote
2answers
75 views

About the pseudo polynomial complexity of the KnapSack 0/1 problem

I have read Why is the dynamic programming algorithm of the knapsack problem not polynomial? and other related questions, so this is not a duplicate but just a related pair of questions to clear some ...
0
votes
0answers
16 views

Probability that BST has exact height

Consider keys $[ 1 \ldots n]$. We want to calculate probability that BST tree has height = $h$. (We assume that distribution is uniform over all $C_{n}$ trees, where $C_n$ - n-th Catalan number). ...
0
votes
0answers
27 views

Number of complete traversals of the circle in generalised Josephus problem?

In the generalised Josephus problem, n people stand in a circle and every kth person is eliminated until only one person is left. The last person left standing can be found using dynamic programming (...
-1
votes
1answer
1k views

Maximum sum path in a matrix

Given a square matrix of size N X N (1 <= N <= 1000) containing positive and negative integers with absolute value not larger than 1000, we need to compute the greatest sum achievable by walking ...
2
votes
1answer
81 views

0-1 Knapsack problem with item discounts

I recently encountered this kind of problem in a real world setting, and could not for the sake of me find any literature relating to the problem statement I came up with. An example will be included ...
12
votes
4answers
12k views

Dynamic Programming vs Memoization

I am having trouble to understand dynamic programming. Mainly because of its name. As far as I understand, it's just another name of memoization or any tricks utilizing memoization. Am I ...
1
vote
1answer
112 views

Recurrence formula for optimal binary search tree

This question is from Section 15.5 of Introduction to Algorithms (third edition). We are given sequence of keys, $ k = \{ k_{1},k_{2},\dots,k_{n} \}$, where $k_{1}<k_{2} <\dots<k_{n} $. For ...
0
votes
1answer
536 views

Longest double increasing subsequence (LIS variant)

I'll start with the definitions:Let $S = s_1s_2...s_n$ be a sequence of $n$ integers. A double increasing subsequence of $S$ is a sequence $P=p_1p_2...p_k$ (not necessarily continuous) where for each $...
1
vote
1answer
112 views

Linear Grammar in less than cubic time

I have a linear grammar $G$ and a string $s$. $G$ is is not limited to right or left linear only but rather has a mix of rules of both types. Is there an algorithm to determine whether $s \in L(G)$ ...
0
votes
0answers
34 views

Optimal partitioning of n-arrays

You're given N integer arrays. Each array can have different size and contains unique values. However same integers can be found in different arrays. The goal is to partition those arrays into K ...
-2
votes
1answer
2k 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
77 views

Why the time complexity for following pseudocode is O(n^2)?

So, I was going through the Rod-Cutting problem in the Dynamic Programming section of the Introduction to Algorithms by CLRS. Here's the rod-cutting problem statement: Given a rod of length n inches ...

1
2
3 4 5
16