All Questions
Tagged with dynamic-programming graph
117
questions
1
vote
1
answer
94
views
Single Source - Single Destination Shortest Path (DFS + DP) - Time complexity?
Context:
I want to write an algorithm for finding the shortest(least cost) path from a fixed source to a fixed destination node in a weighted directed graph with non negative weights (can have cycles)....
- 59
2
votes
0
answers
223
views
minimum number of operations to get a target number
If there is a list of digits in string format, e.g. ["1", "5", "8"], list of valid operations are "+","-", and "*" and a target number. Find ...
- 471
1
vote
1
answer
698
views
Find the number of simple paths from A to B going through a given point on the graph
I am looking into an interesting issue in networks.
Given an undirected graph which can contain cycles:
I choose two points, A and B as origin and end of my paths. My goal is to calculate how many ...
- 15
5
votes
1
answer
110
views
Challenge: How to store a large number of sets to quickly calculate the sum of the values taken by the elements in each set?
I would like to ask for your opinion. Which data structure and algorithm should I use to efficiently solve the following problem?
Question:
Given M(10≤M≤1000) elements and N sets built from these ...
- 51
1
vote
1
answer
121
views
Counting transversal paths in a graph
Given a tree with n vertices, each vertex has a special value C_v. A straight path of length k >= 1 is defined as a sequence of vertices v_1, v_2, ... , v_k such that each two consecutive elements ...
- 13
7
votes
0
answers
294
views
R: Optimally Sharing Cookies Within Groups of Friends
I am working with the R programming language.
Suppose there are 100 people - each person is denoted with an ID from 1:100. Each person can be friends with other people. The dataset can be represented ...
- 5,705
1
vote
2
answers
324
views
Top down approach 01 Matrix
I new do dynamic programming and I am attempting the following problem on leetcode: 01 Matrix
Problem: Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The ...
- 442
1
vote
1
answer
89
views
Maximum non negative product in a matrix
I am trying to solve the following problem on leetcode.com
I found a resource asking a similar question but it didn't yield anything plausible.
I am able to come up with a recursive backtracking ...
- 442
1
vote
0
answers
65
views
optimal path graph algorithm with n movements
I have a graph where each path has a unique a reward. For example, consider the below graph.
A: x => x*1
B: x => x-5
C: x => x*2
D: x => x/5
A
/ \
B --- C
\ /
D
Consider two ...
- 1,152
0
votes
0
answers
84
views
Reconstruct a string from n continuous substrings of fixed length
I have as input a list of n+2 continuous substrings of length 3.
My goal is to find out whether there exists a string of length n such that all its continuous substrings of length 2 are exactly the ...
- 1
1
vote
0
answers
68
views
Count the number of permutations
Hey I'm taking a DS&A course, and we had an interesting homework question regarding counting permutations. The problem is the following:
There is are N(N <= 15) people each with an id from 1 to ...
- 11
1
vote
0
answers
53
views
Algorithm Problem: Finding all cells that has distance of K from some specific cells in a 2D grid [duplicate]
there is a problem I have been thinking on for a while but cannot find efficient algorithm for. it is similar to this problem. I have a 2D grid, some cells with 1, other cells are 0. now I need to ...
- 105
0
votes
1
answer
183
views
How to optimize this graph/tree problem counting distance between two nodes in C++?
Problem is to find sum of distance between two nodes in a tree
INPUT: 6 [[0,1],[0,2],[2,3],[2,4],[2,5]]
shows nodes
OUTPUT: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that ...
- 261
0
votes
1
answer
927
views
Finding array in a matrix
Given an array and a 2d matrix. You have to find if the array is present in the matrix or not.To do so, you can start from any point in the matrix and go in 4 directions that is if you are at (i,j) ...
- 129
1
vote
1
answer
755
views
Min Cost to reach destination using only diagonal moves
Given a infinite grid , we need to find out the minimum cost required to reach a destination from given source. Cost is calculated as below.
Only diagonal movements are allowed.
The cost is ...
- 83