# Questions tagged [dynamic-programming]

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

972 questions
Filter by
Sorted by
Tagged with
37 views

### Efficient Algorithm to Count Permutations of Boss Fights with Divisibility Constraints in an RPG Game

I'm trying to find an efficient algorithm to calculate the amount of permutations for this problem. I've only slightly simplified the problem to be easier to read. But the original problem, is Problem ...
• 330
1 vote
34 views

### Longest non-decreasing contiguous subsequence with at most one substitution

Is there any algorithm that can count the length of the longest non-decreasing contiguous subsequence with at most one substitution? For example, given an array { 1, 7, 7, 2,3, 7, 6,-20}. Find the ...
88 views

### Minimum Cell Changes to Ensure Unique Numbers in Each Row and Column of an $n \times n$ Table

We have an $n \times n$ table, and in each cell of the table, there is a number from $1$ to $2n$. We want to change the numbers in some of the cells and replace them with other numbers from $1$ to ...
131 views

### Minimum number of intervals from a set to cover all intervals of another set

There are two sets of intervals provided to us. target = {{11,13}, {7,10}, {0,3}, {6,6}} space = {{10,12}, {2,6}, {4,8}, {0,4}, {9,10}} I need to find the minimum number of intervals I can pick from ...
• 23
32 views

### Selecting an Induced Subgraph from a DAG with Specific Conditions

I am working with a Directed Acyclic Graph (DAG), denoted as $G$. The graph has a specific constraint where the out-degree of each vertex in $G$ is at most $2$. My objective is to select an induced ...
300 views

### Counting Towers Recurrence Verification From CSES Problem Set

Problem Statement: Your task is to build a tower whose width is 2 and height is n. You have an unlimited supply of blocks whose width and height are integers. For example, here are some possible ...
38 views

### Algorithm to "reverse" search/match pairs from results

Sorry, I don't know how to title it clearly. There is a game, where players can send their units to attack another player's units (weeell, there is a lot of games like that). Each unit has some value. ...
140 views

### Tree algorithm - arrange integer array numbers to form largest number

I have solved leetcode's Largest Number. I am asking another question about it here, more from a theory perspective about "if" I had used a tree for the solution. I have a full functioning ...
• 123
1 vote
28 views

### Algorithms for stacking gage blocks

I'm looking for algorithms for stacking gage blocks. For those unaware, gage blocks are used in machine shops for measuring with high precision and come in sets something like this... Mitutoyo's 56 ...
193 views

### Can every greedy problem be solved using dynamic programming?

Can every problem with a greedy solution be solved using dynamic programming? Why or why not? I'm not completely sure how to formally reason about this, my understanding about the structure of ...
73 views

### Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs

Let $G=(V,E)$ be an unweighted directed acyclic graph with a set $V$ of vertices and a set $E$ of edges. The all-pairs shortest path problem can be solved efficiently using the Floyd-Warshall ...
31 views

### Maximum density knapsack with initial volume and constraint on number of items

Given $\{\rho_i,v_i\}_{i=1}^N$, the densities and volumes of $N$ items, and $K\in \mathbb{Z}_+$. Let $v_0=1$ be the initial volume, and the initial mass is zero. The values $\rho_i,v_i\in \mathbb{R}_+$...
• 101
1 vote
31 views

• 216
1 vote
295 views

### Number of stops during trip - Dynamic programming algorithm

I am attending a course about algorithm design, and I have found an old test which has once been submitted. However, I don't have the solutions to it, and I am having some trouble with one specific ...
1 vote
42 views

### How do I optimally fuse nodes in a tree structure?

I am trying to solve the following problem. I've tried to find the name of this problem, but could not really find what I was looking for. I assume there should be some graph-theory that covers it, ...
• 239
206 views

### is there an efficient algorithm to find the optimal partition of a matrix?

Consider an $n \times n$ matrix of integers. Define a boundary in the matrix to be a sequence of cells, one per x-coordinate, where the y-coordinates of the boundary either stay the same or go up/down ...
• 1,006
23 views

### Generate paths of fixed length across a weighted matrix (defined in $\mathbb{R}$) whose weights' sum falls into given interval

PSSM or PWM (Positional Weighted Matrix) is a common thing in biological science, used often to observe the distribution of letters inside a group of strings of the same length. It's composed by log-...
• 121
1 vote
202 views

### I want to start preparing for a job interviews for which i want to get a decent at solving DSA problems

How to learn DSA if you are already working as a software engineer and have decent knowledge about development. Only thing that makes me procratinate is going over theories behind different data ...
• 119
1 vote
159 views

### Dynamic Programming problem about intervals

This is algorithms and data structures assignment and I have been thinking 3 days about it. You are given N sections, placed on numeric axis. Numeric axis is divided by unit intervals. Each section in ...
32 views

### Intervals with costs and limited resources, dynamic programming

I have been trying to solve the following problem. I have n intervals each with a cost.I want to choose a subset of the intervals that maximizes the cost but with the following constraint. Each ...
• 13
34 views

### Dynamic Program to find well formed set in a rooted tree

You are given a rooted tree $T=(V,E)$ with $n$ nodes and the root $r$. Each node $u\in V$ has an integer label $l(u)$. Suppose $S⊆V$ then $S$ is well-formed if for every $u,v\in S$ if $u$ is an ...
• 139
115 views

### Dynamic programming problem for minimum cost tower placement

I have an algorithmic problem in which I have a highway that is a straight line of length $n$ and a set of unique respective costs for construction of a radio tower for each mile on the highway. I am ...
1 vote
40 views

### How do i make a 2d array as same as i possibly can with another one?

Say i have an 2d array A of nxn size, int values already given for each item.these values can be the same or different. There's gonna be another nxn array B being input. I can only interchange one row ...
14 views

### Better implementations for this dynamic program to solve optimization problem?

In the code below, I describe a problem and provide a backtracking implementation in Python that solves it: ...
• 195
19 views

### Optimize clothing in RPG considering set bonuses

In role playing games, switching equipment for better is a common procedure. My question is to find an algorithm that can optimize linear combination of stats the equipped gear gives - this is exactly ...
35 views

### Knapsack with weight swaps

I have a problem that is 0/1 knapsack, but you are also able to swap the weight of 2 items up to k times. I came up with a O(nkc) solution, but I am looking for a faster o(n*c) solution. I think the ...
84 views

### 3 Processor Scheduling

A set of n independent tasks, each having integer execution times, are to be executed using three identical processors. A task can be executed in any of the three processors. Develop a sequential ...
26 views

### Optimizing an Algorithm for Timestamp-Aware Partitioning of Data

My Problem I'm currently dealing with an algorithmic problem that involves two input lists: A list of natural numbers $[A_1, A_2, \dots, A_n]$ with $A_1, \dots, A_n \in \mathbb{N}$. A list of triples ...
124 views

### complexity of graph matching with order constraint

Given a graph with $n$ vertices and $m$ edges, $m \le {n \choose 2}$, we index the vertices from 1 to $n$, and denote every edge by $(l,r)$ where $1\le l < r \le n$. Find the maximum $k$ such that ...
• 21
38 views

### Find submatrix with sum as close to k as possible

What is the efficient algorithm to find a submatrix (must be rectangle) with a sum that is as close as possible to k? Matrix consists only of nonnegative integers. Iterating through all possible ...
26 views

### Dynamic Programming for LCS problem

I understand that in Dynamic Programming approach the subproblems are solved in a particular order from smallest to largest. In LCS how the subproblems sizes are defined and in which order it is ...
1 vote
413 views

1 vote
71 views

### Maximize sum of matrix after deleting K rows and K columns

You're given a m by n matrix filled with positive integers, as well as some integer k (0 <...
• 111