All Questions
Tagged with dynamic-programming matrix
13 questions
1
vote
1
answer
102
views
Matrix problem, the path that is the flattest
So in this problem I am given an NxN matrix, in which each value of the matrix represents an altitude. I need to find the best path from the top-left corner to the bottom-right one, my moves being ...
3
votes
0
answers
1k
views
Python program to solve matrix-chain multiplication
An assignment at school required me to write a Python program for this task:
In the matrix-chain multiplication problem, we are given a sequence of
matrices ...
- 2,599
5
votes
1
answer
1k
views
LeetCode 01: Matrix challenge
Recently, I've solved the "01 Matrix" LeetCode problem and the solution was accepted by the LeetCode OJ:
Given a matrix consists of 0 and 1, find the distance of the nearest 0
for each cell.
...
- 17.5k
1
vote
0
answers
4k
views
Traceback in sequence alignment with affine gap penalty (Needleman-Wunsch)
I am working on an implementation of the Needleman-Wunsch sequence alignment algorithm in python, and I've already implemented the one that uses a linear gap penalty equation for scoring, but now I'm ...
- 21
0
votes
2
answers
428
views
google foo.bar max path algorithm puzzle optimization [closed]
I got a programming puzzle described as follows:
Save Beta Rabbit
Oh no! The mad Professor Boolean has trapped Beta Rabbit in an NxN
grid of rooms. In the center of each room (except for the ...
- 1
4
votes
2
answers
3k
views
Optimal matrix chain multiplication in Java
Preliminaries
Given two matrices
$$
A = \begin{pmatrix}
a_{11} & a_{12} & \dots & a_{1q} \\
a_{21} & a_{22} & \dots & a_{2q} \\
\vdots & \vdots & \ddots & \vdots \\
...
- 31k
1
vote
2
answers
1k
views
LeetCode Minimum Path Sum algorithm
I am attempting to solve the Minimum Path Sum algorithm problem and I have a working solution, however there was an unwritten requirement that the algorithm not exceed an unspecified amount of time ...
- 188
4
votes
1
answer
949
views
Optimizing a dynamic programming solution for "Oil Well"
I'm trying to solve the Oil Well problem on Hackerrank using dynamic programming and it works. However, it times out for some of the test cases. I wanted to know how this program can be improved so ...
- 195
2
votes
1
answer
232
views
Memoization for calculating minimal traversal distance within a positive matrix
The code below is for calculating the minimal traversing distance from the top left point of the matrix to the bottom right point of the matrix.
GitHub
Here is the core functionality. Please note ...
- 143
4
votes
3
answers
3k
views
Project Euler 81 (minimum path sum through a matrix)
Problem Statement:
In the 5 by 5 matrix below,
131 673 234 103 18
201 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331
...
- 5,220
4
votes
2
answers
344
views
Returning all the LIS of given array of int
I have this assignment where I'm supposed to code an algorithm for finding the quantity of Longest Increasing Subsequences from an array of (different) integers and print them all.
I developed one ...
- 41
1
vote
1
answer
1k
views
MaxSum sub matrix within a matrix
Code review for best practices, optimizations, code cleanup etc. Also requesting verification of the complexity: O(row*row*col).
...
- 8,461
2
votes
1
answer
2k
views
