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

Number of contiguous subsequences summing to a given target

I could not figure out an efficient way (better than $O(n^2)$) to count the number of contiguous subsequences of an array of both positive and negative integers summing up to a given number $k$. For ...
0
votes
0answers
68 views

Multi Knapsack each with different constraints

It seems that there's no end to knapsack variations… here's the one I bumped into (at work): There are: N items, each with the usual value and weight properties. M bins, each with an upper ...
2
votes
2answers
90 views

Reduce the total internal border of a set of touching rectangles (using graphs)

I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum ...
2
votes
1answer
105 views

How to find efficiently the minimum modification to avoid close consecutive numbers?

I have an array of sorted numbers: arr = [-0.1, 0.0, 0.5, 0.8, 1.2] I want the difference (dist below) between consecutive ...
1
vote
1answer
90 views

What is the optimal way to solve the following optimization problem

You are given a function $F$, which can take one or more positive integer operands. Let $L=\{a_1,a_2\ldots a_n\}$. We need to compute the function $F(L)$ using the least number of transformations/...
12
votes
2answers
272 views

Word factorization in $O(n^2 \log n)$ time

Given two strings $S_1, S_2$, we write $S_1S_2$ for their concatenation. Given a string $S$ and integer $k\geq 1$, we write $(S)^k = SS\cdots S$ for the concatenation of $k$ copies of $S$. Now given a ...
2
votes
1answer
150 views

What is the optimal way to perform GCD chain operation?

Matrix chain multiplication problem:- Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. This problem is solved using dynamic programming. Similarly ...
2
votes
0answers
32 views

What are the pros and cons of context-oriented programming (COP)?

I have started reading about COP, but can't really get a grip of it. What I understand is that you use layers to let the software dynmically adapt depending on the context, and this would result in ...
1
vote
1answer
224 views

How to minimize the average distance between pumps and cities?

There are n cities [1, 2, 3, .... n] and k available pumps. These pumps can be installed in k...
2
votes
1answer
832 views

DP recurrence relations: Coin change vs Knapsack

Take: KP recurrence relation $ max { [v + f(k-1,g-w ), f(k-1,g)] } $ if w <= g and k>0 CCP recurrence relation $ min {[1 + f(r,c-v), f(r-1,c)]} $ if v <= c and r>0 I don't ...
0
votes
0answers
162 views

Intuition behind Floyd-Warshall being faster

I know the Floyd-Warshall, and I also clearly understand the proof of running time of $O(V^3)$ of F-W algorithm. However, consider this algorithm: Let $dp[i][j][n]$ denote the shortest path from $...
0
votes
0answers
49 views

What will be an O(n) solution for this?

Suppose a given piece of work can be done at two processors. One at r and another at v. The job can run only at one processor at ...
2
votes
3answers
869 views

Algorithm to find smallest number divisible by N with sum of digits as N

Problem: Given $N$, find the smallest number divisible by $N$ whose sum of digits is equal $N$. For example: $n = 1$, answer is $1$ $n = 10$, answer is $190$ There is some dynamic programming ...
1
vote
1answer
316 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
1answer
48 views

Sum of zero nim sum series

The problem is proposed here and related to this question. Given $n$ and $k$, I would like to know how to compute$$\sum_{\substack{x_0 ⊕x_1⊕\cdots⊕x_k=0\\x_i≥0,\ 0≤i≤k\\\sum\limits_{i=0}^kx_i≤n-2k}}\...
1
vote
0answers
79 views

Possible Distribution of coins

We are given a set of $n$ coins with denominations $v_1,v_2,\ldots,v_n$ and a number $x$. The coins are to be divided between to persons, with the restriction that each person's coins must add up to ...
2
votes
0answers
74 views

Balls in Bins with Pairwise Distance

Given $n$ bins in a row (numbering from $1$ to $n$) and $2k$ balls ($n \ge 2k$), one may put all balls into bins with each bin having at most one ball (there are $\binom{n}{2k}$ configurations). ...
1
vote
1answer
528 views

Algorithm Design for Linear Programming

I am trying to complete question and would like to avoid copying answers, but I do not necessarily understand what I am doing. I am working on the following problem: Suppose you are consulting ...
1
vote
1answer
479 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
0answers
183 views

Tail recursion can't work with dynamic programming programs

I am doing some exercises on dynamic programming in order to get familar with this concept. I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
2
votes
1answer
59 views

Making a profit as a high-dimensional store owner?

Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient. Let's say that I am some business owner with a set of $...
4
votes
3answers
6k 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
168 views

Help writing a dynamic programming algorithm in English

It’s Friday night and you have $n$ parties to go to. Party $i$ has a start time $s_i$ end time $t_i$ and a value $v_i \ge 0$. Think of the value as an indicator of how excited you are about that party....
0
votes
1answer
87 views

Grid Based DP: How do we tweak the Travelling Salesman Problem to work with Grids

The question is: There is a n x n grid (Maze) which has either 0, 1 or 2. 0 means a path exists, 1 means the cell is blocked and 2 means there exists gold in that cell. Task is to start from 0,...
2
votes
1answer
211 views

How to find the number of Binary Search Trees with given number of nodes and leaves?

With 7 nodes of distinct values (unique), how many Binary search trees (BST) can be formed such that: Exactly $1$ leaf node(s) present? Exactly $2$ leaf nodes present? I was able to solve the first ...
2
votes
1answer
49 views

longest sub-sequence in both directions

Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A. Example: A = cabca the sub-sequence S = abc is the ...
2
votes
2answers
57 views

How can I reduce the time of this program

I solved a problem similar to the knapsack problem. There are two packages with a capacity of $P$ on a production line. We want to put $N$ items in them with the weights $w_1,...w_n$ in a pre-defined ...
2
votes
1answer
443 views

The number of balanced trees with N node and L leaves

An algorithm is requested to calculate all balanced binary trees which can be built with $N$ nodes, having exactly $L$ leaves. A balanced tree is a binary tree in which the difference between the ...
-1
votes
2answers
598 views

How can I write this backtracking algorithm using dynamic programming?

Problem: There are $n$ points on a map, $p_1,..p_n$. There are two officers located initially at $(0,0)$ coordinate. They want to patrol all of these points with a minimum traveling (each officer ...
1
vote
0answers
299 views

Given a binary tree of leaves with weights, find minimum weights for internal nodes (such that sum(weighti-weightj) is minimized for (i,j)∈E(T))

So this is a question within a bigger question for which I've reduced to this so far: If I have a tree (phylogenetic) with known weights for leaves, how would I find the weights for all internal ...
2
votes
0answers
134 views

Weighted Sorting Algorithm

Given a permutation of $n$ element and for each pair of position $i$ and $j$, a non-negative integer $c_{ij}$ which is cost of swapping $i$-th element and $j$-th element of permutation. Is there any ...
1
vote
1answer
61 views

Can the compiler convert recursive algorithm into a dynamic programming

So I was going through the idea behind dynamic programming (memoization), and thought of this question. Can a compiler convert any recursion into a table filling DP solution, of course given the ...
1
vote
1answer
61 views

Optimizing the problem

I have a recurrence relation: $$f(a,b) = \begin{cases} 1 & (a,b) = (0, 0)\\ 1 & (a,b) = (a, 0)\\ 0 & (a,b) = (0, b)\\ 2a & (a,b) = (a,1)\\ f(a-1,b) + f(a-2, b-1) + f(a-1,b-1)...
0
votes
1answer
280 views

Finding recurrence relations for dynamic programming algorithms

Consider a function $f(n)$ whose definition requires one to compute $f(1),f(2),..f(n-1)$ in order to evaluate $f(n)$. Suppose that some algorithm to compute $f(n)$ has time complexity that is given by ...
1
vote
2answers
172 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
203 views

Minimum Number of Integers From a List that Add up to N (Dynamic Programming)

A problem I'm working on requires me to find the minimum # of integers from a given list that add up to $N$, or more specifically: Given a list $L$ of $K$ integers, $[a_1, a_2, ... , a_k$], where ...
0
votes
1answer
78 views

Maximum trailing zeros of the path

Problems: A table with $n$ rows and $m$ columns is filled with number from $1$ to $100$ (duplication allowed). The player starts at $(1, 1)$. He can only move right or down. The goal is to reach $(n, ...
1
vote
1answer
666 views

How does the problem of “Scheduling to Minimize Lateness” exhibit optimal substructure?

The problem of "Scheduling to Minimize Lateness" is as follows (Section 4.2 of the book "Algorithm Design" by Jon Kleinberg and Eva Tardos): Input: A finite set $J = {J_1, J_2, \ldots, J_n}$ of $n$ ...
2
votes
1answer
139 views

Graph Traversal Solutions for “Find all unique paths” Problem

I was studying the grid problem where a robot is at the top left position and wants to go to the bottom right position and you need to return the number of unique paths it can take to get there with ...
2
votes
1answer
193 views

Optimal substructure and dynamic programming for a variant of the rod cutting problem

The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following. Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the ...
1
vote
1answer
254 views

No. of subsets whose element multiply to give a square number

I have been given an array whose elements lie between [1,70] and the size of array [1,10^5]. I have to find the total number of subsets whose all elements multiply to give a perfect square number. ...
2
votes
1answer
36 views

Count number of the ways to fill a N-lengthed binary string

From the problem, count the number of ways to fill a binary string of length $N$ with at least one $1$'s consecutive sequence of length $K$ and other $1$'s consecutive sequences have length no more ...
2
votes
1answer
401 views

Maximum Equal Sum K Subsequences

Given an array we need to find maximum equal sum $K$ subsequences, i.e. we want the sum to be maximized such that there are exactly $K$ non-overlapping subsequences each having the same sum. Example: ...
1
vote
1answer
62 views

How to implement recursive solution with large number or parameterized possible next steps

I was looking at a recursive solution for the robot on a grid problem which basically states that there is a robot on the top left corner on a grid and you are supposed to find a path to the bottom ...
3
votes
1answer
291 views

Request for examples to show various types of subproblems in dynamic programming

Chapter 6 of "Algorithms" by Dasgupta, Papadimitriou, and Vazirani summarizes four types of subproblems that are quite common in dynamic programming. They are prefix/postfix of a string/sequence/...
1
vote
1answer
146 views

Recursive DP vs Graph Traversal solutions to path-based problems

I am studying some algorithms interview questions and I am seeing many path-based questions like "if a robot is at the top left of a grid and can only move down or to the right, how many paths can ...
2
votes
2answers
2k views

Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T. This question is a simplification of ...
1
vote
0answers
134 views

Parenthesizing a product using dynamic programming

Here is a problem that I've been given to solve in time $O(n^2|\Sigma|)$. Given an alphabet $\Sigma$ and the product of every two elements in this alphabet (i.e., an arbitrary mapping $\cdot\colon ...
1
vote
2answers
1k views

Understanding algorithm for maximum sum of non-consecutive elements

There is a well-known problem in CS of finding the maximum sum of non-consecutive integers in a list. There is even an SO post about how to solve it: https://stackoverflow.com/questions/4487438/...
3
votes
0answers
50 views

Sequence matching

Let $T$ and $P$ be respectively two sequences $t_1, · · · , t_n$ and $p_1, · · · , p_k$ of characters such that $k ≤ n$. The characters range over a finite alphabet Σ. With each position of $T$, we ...

1 2 3 4 5 13