All Questions
Tagged with dynamic-programming java
60 questions
12
votes
5
answers
7k
views
Dynamic programming with Fibonacci
I have written the following code using a dynamic programming technique. Can I use ArrayList here? Please let me know if I can improve this code.
...
- 665
12
votes
2
answers
640
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
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 any ...
- 231
11
votes
3
answers
1k
views
Optimizing "Herd Sums" problem using dynamic programming
I'm trying to solve a practice problem and all is well except for the last 2 inputs my solution is too slow. Just one loop is slowing it down I think.
Herd Sums
Execution Time Limit: 2 seconds
...
- 213
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
10
votes
1
answer
4k
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,984
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, ...
8
votes
2
answers
913
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 ...
8
votes
1
answer
2k
views
Assembly line scheduling
This is solution to the assembly line problem. Here is complete description, which is too big and verbose to re-describe. I apologize for the inconvenience of the hyperlink.
Note: I do understand ...
- 8,451
7
votes
2
answers
4k
views
Finding alternating sequence in a list of numbers
Please be brutal and treat this as me coding this up for an interview.
A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between ...
- 2,236
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
5
votes
3
answers
962
views
LeetCode 678: Valid Parenthesis String, Recursion memoization to DP
How can the following recursion + memoization code be converted into a tabulation format dynamic programming solution?
The code is working, but I want to improve it.
The challenge I am facing is ...
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
5
votes
1
answer
573
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
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