Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
1
vote
1answer
30 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...
0
votes
1answer
20 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
44 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
26 views
Dynamic Programming : Recovering Optimal Solution: Refer Tardos
"So far we have simply computed the value of an optimal solution; presumably
we want a full optimal set of intervals as well. It would be easy to extend
M-Compute-Opt so as to keep track of an optimal ...
0
votes
0answers
46 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
46 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 ...
0
votes
1answer
45 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
0answers
19 views
Find largest subset of compatible indices using $O(n^2)$ DP algorithm
Past year paper question
We are given a set $S$ of $n$ pairs of real numbers $S = \{(a_1,b_1),...,(a_n,b_n) \}$ such that $a_1 \leq a_2 \leq ... \leq a_n$. We say that a pair of indices $(i,j)$ is ...
0
votes
0answers
14 views
counting subsequence with distinct elements in the group
how to solve it using dynamic programming?
suppose if i have an array and containing elements between 0 and 5 and elements are repeated more than once i want to find the no of subsequences with ...
0
votes
1answer
38 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}}\...
0
votes
0answers
13 views
What are “self-adjusting computation” and “dynamic programming”, and how are they different?
According to this website:
Self-adjusting computation refers to a model of computing where
computations can automatically respond to changes in their data
The papers linked on this page make ...
1
vote
0answers
29 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
58 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
43 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 ...
0
votes
0answers
22 views
Can any recursion implementation be written into a bottom-up DP implementation?
Can any top-down recursion implementation be written into a bottom-up DP implementation?
1
vote
1answer
49 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
20 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 ...
0
votes
0answers
18 views
Given graph with N nodes colored in K colors, count paths visiting each color exactly once
Let's say we have given graph of at most $N = 400$ nodes, and each node is colored in one of $K = 21$ colors. We need to count paths of length $K$, such that each node on the path is in one of the $K$ ...
2
votes
1answer
44 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 $...
1
vote
3answers
87 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 ...
0
votes
1answer
102 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
17 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,...
1
vote
1answer
28 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
33 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
51 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 ...
0
votes
0answers
61 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
139 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 ...
0
votes
0answers
45 views
How we can minimize number of boxes for packing objects
Imagine we have n objects with different weights.
We know the order in which objects come into the packing machine. Packing machine have two boxes, their capacity are equal and constant. When an ...
1
vote
0answers
30 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
28 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
36 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 ...
0
votes
1answer
28 views
Optimizing the problem
I have a recurrence relation:
f(a,b) = f(a-1,b)+f(a-2,b-1)+f(a-1,b-1)
with conditions:
f(0,0)=1, f(a,0)=1, f(0,a)=0, f(x,1)=2*x
where the constraints: 1<=a<...
0
votes
0answers
17 views
Reach the nth stair using step a-b while some stairs are broken
Description
A person is standing below at a staircase having $N$ steps. Considering he can take a leap of between $a\geq1$ and $b\leq N$ steps at a time. In the meanwhile, some of the stairs are ...
0
votes
1answer
19 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
44 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
57 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
21 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
94 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
22 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 ...
1
vote
1answer
45 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 ...
2
votes
1answer
35 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
26 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
130 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
22 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
82 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
22 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
295 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
70 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 ...
0
votes
2answers
49 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
46 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 ...
