All Questions
Tagged with dynamic-programming java
60 questions
1
vote
3
answers
128
views
Another ATMs cash-out (denomination) algorithm in Java
Related to this question and this answer, I would like to have a second review from you on a modified version.
The problem I tried to solve
Some kind of "Minimum count of numbers required from ...
- 628
3
votes
1
answer
4k
views
Count the number of distinct subarrays
I want to determine the number of distinct subarrays that can form having at most a given number of odd elements. Two subarrays are distinct if they differ at even one position. The subarray is a ...
- 31
4
votes
1
answer
164
views
Searching for an idiomatic Rust implementation of Minimum Edit Distance (LeetCode #72)
I am solving LeetCode Dynamic Programming challenges (this one is #72, at https://leetcode.com/problems/edit-distance).
Here below, I've implemented a Rust solution for the minimum edit distance ...
- 143
1
vote
1
answer
832
views
Maximum subset sum with no adjacent elements
Write a function that takes an array of integers (Both Positive and negative) and return the maximum sum of non adjacent elements. Note that even if all values are negative, I don't have an option to ...
- 185
2
votes
2
answers
82
views
(Java) Read .txt and organize activities for hours / minutes
Doubts in logic to generate the output file according to the example
I need that even if he reaches the total_min <720 condition he continues to travel the lines. 720 is the total number of minutes ...
- 123
3
votes
2
answers
2k
views
LeetCode: Longest String Chain (Java)
For the question, I had a pretty messy solution so I would like some advice on how to better use Java to make the code a bit cleaner.
Also, a semi-hack that I did that I'm not proud of is checking if ...
- 85
5
votes
2
answers
124
views
Calculate the rates at which users get stuck at each stage
I completed an algorithm problem just as a personal study, and I can't help but feel like my solution is a bit needlessly complicated, although I can't figure out a better way to do it. Here's the ...
- 151
3
votes
2
answers
823
views
Optimal burger-eating challenge
Little history to give context to the problem:
The Krusty-Burgers
Homer Simpson is a smart guy who likes to eat Krusty-Burgers, and it takes m minutes for Homer ...
- 391
0
votes
2
answers
503
views
Making Anagram Problem Implementation
Problem Statement
Alice is taking a cryptography class and finding anagrams to be very useful. We consider two strings to be anagrams of each other if the first string's letters can be rearranged to ...
- 489
3
votes
2
answers
1k
views
Counting the number of ways to decode a string
I am working on problem where I need to decode a string:
A message containing letters from A-Z is being encoded to numbers
using the following mapping:
'A' -> 1
'B' -> 2
...
...
- 499
3
votes
2
answers
254
views
Longest common subsequence solution
I've seen this today on a mock interview and wanted to give it a try. I'd love to hear some feedback from you guys. This is my second attempt at the problem, initially I had a mess of ...
- 316
2
votes
1
answer
64
views
Number of way to render an amount of money
I made an algorithm to train my skill in dynamic programming and I would like to have feed back on it. This algorithm takes a money system (int) and have a certain ...
- 21
3
votes
1
answer
10k
views
Solving maze problem with backtracking solution using stack
I solved the maze backtracking question using a stack however could not find any other solution like that anywhere (to validate my solution is actually a valid one).
The problem statement is as ...
- 143
3
votes
2
answers
921
views
Memoized solution to Count number of ways to climb n steps
Problem statement : A Child is climbing up n steps with either 1 , 2, 3 hops ..how many ways can the child climb up the stairs?
source: cracking the coding interview book.
I have two solutions the ...
- 501
0
votes
2
answers
949
views
Number of Paths (BackTracking) in Java
Illustration
You're testing a new driverless car that is located at the Southwest
(bottom-left) corner of an n×n grid. The car is supposed to get to the
opposite, Northeast (top-right), corner ...
3
votes
2
answers
65
views
Splitting uppercase letters based on a dictionary
A few days ago I learned about the dynamic programming approach to problem-solving; the thing is, I'm still not sure I am fully grasping the concept.
I decided to write an algorithm that takes a ...
- 31
2
votes
0
answers
50
views
Optimizations for Knapsack with 3 dimensions
Problem Statement:
I am given a set of prices for \$n\$ items I have to find out what is the maximum value I can get with \$M\$ money by selecting exactly \$C\$ items without exceeding the amount of ...
- 171
3
votes
0
answers
147
views
Convert top-down subset sum to bottom-up
I have written the code for calculating subset-sum and also printing the first encountered non-empty subset from the left that sums up to the given sum.
My code in Java is as follows:
...
- 171
3
votes
2
answers
4k
views
"What is the fastest solution for finding the maximum sum of a subarray?"
Question
Given an array, find the longest continuous sub-array which has maximum sum.
My Approach
First, I solved this problem using dynamic programming which effectively solved the problem in \$...
- 283
3
votes
1
answer
435
views
Find the maximum possible summation of differences of consecutive elements
Array A contains the elements, \$A_1,A_2, \ldots, A_N\$.
And array B contains the elements, \$B_1,B_2, \ldots, B_N\$.
There is a relationship between \$A_i\$ and \$B_i\$: any element \$A_i\$ ...
- 261
2
votes
1
answer
1k
views
Coin Change Problem with Memoization
Purpose
Another take on the classic Change-making Problem:
Given some set of coins and a value, find the minimum number of coins necessary to add up to this value
In my implementation, instead of ...
- 1,855
0
votes
1
answer
296
views
Count number of ways to achieve a sum [closed]
The Question :
Utkarsh being a very talkative child, was scolded by his teacher
multiple times. One day, the teacher became very angry and decided to
give him a very rigorous punishment. He ...
- 231
2
votes
1
answer
2k
views
Regular Expression Matching: Recursive and DP-based implementation
Problem Statement:
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching ...
3
votes
0
answers
57
views
Number of ways to complete a plan
I worked on a dynamic programming problem. Here is its link. I have to find the number of ways respecting the constraint that user doesn't go to the Gym for two consecutive days.
...
- 265
2
votes
1
answer
467
views
Find the length of the longest Common Subsequence
I have a DP based implementation for the Longest Common Subsequence(LCS) problem
to find the length of the LCS.
I wanted to know if there is room for improvement in terms of efficiency(space/time).
...
- 501
1
vote
2
answers
81
views
NAddOdd - Topcoder - Single Round Match 714 Round 1 - Division I, Level Two
I am interested in DP problems from the past couple of days and am trying to solve various problems on topcoder. To be very frank could not even solve a single one till now. I went through https://...
2
votes
1
answer
1k
views
Coin change with Dynamic Programming
I have made an implementation of coin change problem solved with Dynamic Programming. Could you guys help with renaming some method and variables?
Here is my implementation -
...
- 496
4
votes
1
answer
272
views
Assembly Line Scheduling challenge, solved using TDD
I am new to Test Driven Development and currently practicing it with some problem statement. Following is an Assembly Line Problem statement I solved using TDD approach in java. Please provide me some ...
- 265
3
votes
1
answer
111
views
Given two words, transform the first one into the second [closed]
As the title says, the problem I had to do sounded something like this:
We are given two words, S1 and S2. We must transform S1 into S2, using the following operations:
insert: insert a character in ...
- 31
1
vote
2
answers
284
views
SPOJ - Alphacode - Exceeds Time Limit
I'm trying to solve Alphacode on SPOJ. The challenge is to count the ways to split a string of up to 5000 digits into a sequence of numbers, each ranging from 1 to 26.
It works fine for small ...
- 189
5
votes
1
answer
572
views
Snakes and Ladders using a magic die
This is a problem from here where you're given a magic die, and the objective is to find the minimum number of dice throws (hops) to go from the start point to the end of the board, and win the game.
...
- 51
8
votes
5
answers
2k
views
Repeatedly partitioning an array equally as far as possible
I solved HackerRank Nikita and the Game. The implementation is correct as program passes all test cases.
Nikita just came up with a new array game. The rules are as follows:
Initially, ...
6
votes
1
answer
3k
views
Coin change algorithm
I've implemented the coin change algorithm using Dynamic Programming and Greedy Algorithm w/ backtracking. The description is as follows:
Given an amount of change (n) list all of the possibilities ...
- 181
2
votes
2
answers
5k
views
Candie distribution algorithm
I am studying algorithms and I solved this problem under Dynamic Programming section:
Alice is a kindergarten teacher. She wants to give some candies to the
children in her class. All the ...
- 287
1
vote
1
answer
2k
views
Levenshtein distance with edit sequence and alignment in Java
I have this program that computes a Levenshtein distance of the two input strings, their edit sequence, and the alignment:
LevenshteinEditDistance.java:
...
- 29.8k
0
votes
1
answer
964
views
Longest contiguous Increasing Subset in java
I have tried to come up with a solution to the longest increasing subsequence problem.Can this solution be optimized further?
Example 1:
Input: {5,4,3,7,8,9,11}
Output: 3, 7, 8, 9, 11
Example 2:
...
2
votes
1
answer
415
views
An iterator returning all possible solutions to n-queen problem in Java - follow-up
(See the initial iteration.)
Now I have slightly improved performance of the iterator. Whenever we have set a queen at a particular board cell, the previous iteration sacrifices \$\mathcal{O}(n)\$ ...
- 29.8k
2
votes
1
answer
201
views
0-1 Knapsack in Java
I'm looking for advice on coding practices in general.
...
12
votes
2
answers
637
views
Dynamic Programming: Fibonacci-like recurrence relation
This is a problem from my Introduction to Algorithms textbook.
Consider the infinite sequence of numbers An|n>0 = (1,1,3,4,8,11,...) defined recursively as follows.
$$
A_n = \left\{\begin{aligned}
&...
- 9,839
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 \\
...
- 29.8k
8
votes
2
answers
910
views
Quick Sum TopCoder (Brute Force solution)
Given a string of digits, find the minimum number of additions
required for the string to equal some target number. Each addition is
the equivalent of inserting a plus sign somewhere into the ...
12
votes
1
answer
441
views
Counting paths in an n-dimensional grid that stay within the boundaries
Problem Statement
You are situated in an N dimensional grid at position (x1, x2, …, xN).
The dimensions of the grid are (D1, D2, …, DN). In one step, you can
walk one step ahead or behind in ...
- 231
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
10
votes
2
answers
300
views
Undo format when format disappears
I was posed a question as follows:
Given a sentence like "John is a bad man", lets say all the formatting disappears and you are left with one string "johnisabadman". Given a dictionary of words, ...
- 1,213
4
votes
2
answers
6k
views
Finding all the subsets in an array of integers that sum to a given target
Problem Statement:
Given an Array if ints, Find out all the subsets in the Array that
sum to a given target value.
Example:
If the input array is:
...
- 872
2
votes
1
answer
2k
views
Solving the rod-cutting problem using dynamic programming
I've written what I believe is a valid dynamic programming solution to a variation of the rod cutting problem. In this problem, the goal is to make as few cuts as possible on a rod of length n.
I ...
- 29
1
vote
0
answers
2k
views
DP algorithm to find minimum average wait for customer-serving system
Below is the code to find the minimum average waiting time for customers at a store. I want improve the time complexity of the code. As an overview of the logic, I start from ...
- 223
1
vote
1
answer
2k
views
Coin problem through brute force
I have some code that will brute force solve the following problem:
Given a set of x coins and a target sum to reach, what is the fewest number of coins required to reach that target?
The code so ...
- 3,032
10
votes
1
answer
3k
views
Project Euler #14 -- longest Collatz sequence
I was reading this question and realized that I didn't know Python well enough to critique the algorithm. So I wrote a Java solution instead, which is inappropriate for that question. Since there's ...
- 6,974
2
votes
2
answers
468
views
Calculating the number of prime numbers to solve the puzzle
How can the following program execution time improved? I have used dynamic programming in both "recursive" as well as "prime" function, but I'm not getting the efficient execution time.
There is a ...
- 63