# Questions tagged [dynamic-programming]

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

595 questions
Filter by
Sorted by
Tagged with
16 views

### Whats the name of the library for dynamically choosing a sorting algorithm?

I got tired of googling for it, IIRC Facebook or Google created a library that explored the data before deciding which algorithm to use, I thought it was called F15 or something. it made some insights ...
106 views

### Thought process to solve tree based Dynamic Programming problems

I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems ...
36 views

### A deck drawing problem

Given two decks of cards (ammount of cards in each deck is n) where each card holds a character, removing a card from the top of one of the decks counts as one action. If both decks show the same ...
57 views

### Dynamic programming

Got a question and can't manage to find an answer, so help will be appreciated. I should design an algorithm, using dinamic programming, that gets as an input a matrix, named A, with n rows and k ...
37 views

### Maximum number of similar groups of a given size that can be made from a given array

I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by $B$ and the size of the group be $A$. I need to find the maximum number of groups with the ...
242 views

### Find if there is matrix that satisfying the following conditions

Given a matrix $A_{n\times n} = \{a_{ij}\}$ such that $a_{ij}$ is a non-negative number and given 2 vectors $(r_1,r_2,...,r_n)$ , $(c_1,c_2,...,c_n)$ such that $r_i,c_i\in \mathbb{Z}$ define an ...
33 views

### What are some variants of the rod cutting problem?

I am looking at the possible implementations for solving the rod cutting problem (CLRS). Do you know of any variants of this problem and their use in industry?
39 views

### A variant of the knapsack problem

Consider the following variant for the knapsack problem: the input are disjoint sets of items $T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
734 views

### min vertex cover to access k edges in a tree

I need to find the minimum number out of $N$ vertices on a tree with $N-1$ edges, so that at least $K$ edges of that tree are connected to these vertices. For example, if $N=9$ and $K=6$ and we have ...
78 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 ...
29 views

### Schedule a Seminar in Minimum Time

There are t1, t2, t3,.....,tn topics which are to be scheduled in a building with c1,c2,c3,....ck halls. Members have already registered there interests on the topics, and they have liberty to choose ...
94 views

### Given n sorted arrays with size k select one element from every array such that the sum of the elements is minimum and the sum of their indices is k+1

So if $k = 3$ and $n = 2$ and we select the element $a_1$ of the first array then we have to select $a_2$ from the second array. If we select the element $a_1$ then also $a_2$ must be ...
36 views

### (Leetcode) Combinatorial Sum - How to generate solution set from number of solution sets?

The following question is taken from Leetcode entitled 'Combination Sum' Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique ...
128 views

### Counting number of paths between two vertices in a DAG

I need an algorithm that computes the number of paths between two nodes in a DAG (Directed acyclic graph) I need a dynamic porgramming solution if possible.
51 views

### Optimal ordering - Dynamic programming on subsets

We have a set T of n elements and m subsets $R_i \subset T i = 1,...,m$. The $S_i$ are not assumed to be different. We also define an ordering of T, a one-to-one mapping $\pi$ of $T$ onto the set of ...