Questions tagged [dynamic-programming]
Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
1
vote
0answers
36 views
Is MCTS an appropriate method for this problem size (large action/state space)?
I'm doing a research on a finite horizon decision problem with $t=1,\dots,40$ periods. In every time step $t$, the (only) agent has to chose an action $a(t) \in A(t)$, while the agent is in state $s(t)...
1
vote
1answer
45 views
Can Dynamic programming be applied to solve problems if and only if the subproblem form a DAG?
I assume Dynamic Programming can be used only when the corresponding subproblems form a Directed Acyclic Graph, otherwise you're stuck in a loop.
Is this reasoning correct or is there more to it?
1
vote
0answers
23 views
Count paths in matrix that visit each number exactly once
Let's say we are given matrix of size $N \leq 21 \text{ by } M \leq 21$ each element of the matrix is either $-1$ or number in the interval $[0, 20]$.
We want to count the number of paths that start ...
2
votes
2answers
39 views
Technique for converting recursive algorithm to DP
I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed).
But, I'm unable to convert my recursive code to <...
2
votes
4answers
64 views
1
vote
2answers
42 views
set cover where only certain special subsets are allowed
I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
1
vote
0answers
64 views
Maximize interleaving subsequences two digit arrays/strings
Suppose I have two digit arrays, A and B as follows
A = [3,4,5,6]
B = [9,8,3]
Now, I have ...
2
votes
1answer
29 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 ...
1
vote
1answer
41 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
16 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
73 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
80 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
76 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/...
11
votes
1answer
189 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 ...
1
vote
1answer
54 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
23 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
41 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
24 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
49 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
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
53 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
51 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
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
20 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
37 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
28 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
52 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
22 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
20 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
46 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
104 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
107 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
23 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
37 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
83 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
146 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
59 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
47 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
32 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
39 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
32 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
1answer
24 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
61 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
60 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
23 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
139 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$ ...
