# Questions tagged [dynamic-programming]

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

758 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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. ...
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. ...
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 ...
403 views

Different machine has different efficiency on different tasks, like: ...
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 ...
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 ...
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+...
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 ...
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 ...
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 ...
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 ...
112 views

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)$ ...
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 ...