Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.
-3
votes
0answers
13 views
Accommodating Existing Code for Vectors as Opposed to Arrays [on hold]
I don't have much experience with vectors so I have no idea how to accommodate the code I've written over the last two days for vectors. I realize the code structure is kind of all over the place, but ...
5
votes
1answer
84 views
Hackerrank: Lucky Number Eight (Dynamic Programming)
Problem statement
Given an n-digit positive integer, count and print the number of subsequences formed by concatenating the given number's digits that are divisible by 8. As the result can be large,...
2
votes
2answers
38 views
High execution time on number partitioning program in Python 2.7
I am writing a program to count only the partitions of a number with distinct parts.
I am using a bottom-up approach to dynamic programming to generate partition lists from previously obtained ...
6
votes
2answers
129 views
UVA 100: “The 3n + 1 problem”
I’ve solved UVA Problem 100: The 3n + 1 problem . In short, the task was to write a program that calculates a maximum of Collatz sequence lengths for any given range of starting values.
My program:
<...
3
votes
1answer
77 views
Dynamic programming solution for cross river algorithm (part 2)
I'm working on the cross river problem (previous post here). Any advice on performance improvement in terms of algorithm time complexity, code bugs or code style advice is appreciated.
More ...
5
votes
1answer
88 views
Dynamic programming solution for cross river algorithm
Working on below cross river problem, and post my code in Python 2.7 using dynamic programming. Any advice on performance improvement in terms of algorithm time complexity, code bugs or code style ...
3
votes
0answers
56 views
Hackerrank: Sherlock and anagram (optimal time complexity)
Problem statement
Given a string \$S\$, find the number of "unordered anagrammatic pairs" of substrings.
Input Format
First line contains \$T\$, the number of testcases. Each testcase ...
3
votes
1answer
110 views
Guess number with lower or higher hints
Problem statement
Two players - Alice and Bob. Alice needs to guess a number \$n\$, from
range \$[1, N]\$, \$N \le 200\$
In \$i\$th turn, Alice guesses a number \$i\$
Bob chooses to ...
1
vote
1answer
131 views
Implementation of Wagner-Fischer-algorithm
I'm working on an implementation of a Wagner-Fischer-Algorithm for an online programming challenge site, but I can't seem to push the time down to where it needs to be. The assignment is to, for a ...
3
votes
0answers
22 views
Uses subproblems to solve large problem (maximization of value within space)
If this question is not a good question for this board, I will remove it. I am looking for ideas on how I could improve the code as I am a beginner trying to learn how to program.
Here I have a ...
4
votes
1answer
75 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 ...
4
votes
1answer
96 views
Different path for grid move
Given a m * n grids, and one is allowed to move up or right, find the different number of paths between two grid points.
My major idea is, if move r steps right, <...
3
votes
1answer
71 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 ...
1
vote
2answers
50 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 ...
5
votes
1answer
64 views
Dynamic attribute key selector
I'm basically trying to build a function that searches all nodes on the DOM to check for data attributes, then swap them out with whatever is stored with the "data-intl-" attribute. For example, if ...
0
votes
0answers
81 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 ...
3
votes
0answers
66 views
Word Wrap via Dynamic Programming
Word Wrap problem in short:
Given n words and a line length, break the words into lines in such a manner that minimizes the sum of the costs of all the lines. Consider the cost of each line being (...
3
votes
1answer
84 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.
...
7
votes
2answers
134 views
Justify text from a file using a LaTeX method
I wrote a bit of code that takes a file, justifies the text and writes to another file.
It uses a DP approach to minimise a badness metric, which is the amount of under or overshoot of the line ...
3
votes
1answer
172 views
Python graph challenge
I'm looking for ways to optimize a function that I wrote as an answer to this problem in Python:
You and your rescued prisoners need to get out of this collapsing death trap - and fast! ...
6
votes
4answers
126 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, ...
1
vote
1answer
147 views
Longest common substring using dynamic programming
I've written a short python script that attempts to solve the problem of finding the longest common substring using the dynamic programming technique. It is meant to be generalised so I could plug in ...
4
votes
1answer
106 views
Hackerrank “Bricks Game”
Problem URL
This is the solution I came up with the minimax problem stated above. I did a top-down recursive approach with memoization, and I think this should be \$O(n)\$, since we are filling out a ...
1
vote
3answers
265 views
Code for calculating best possible combination in an array
The problem here , requires me to find the best possible combination of values in an array which is nearest to 0 and are adjacent to each other , here is an little excerpt from it,
The government ...
4
votes
2answers
184 views
Edit distance implementation
This problem is taken from the book Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein:
In order to transform one source string ...
1
vote
1answer
95 views
Find the Longest Subsequence using Dynamic Programming
Attempting to learn dynamic programming, it seems like the algorithm works. I'm looking to make sure the algorithm is correct (and actually uses dynamic programming correctly) and for pointers on ways ...
4
votes
0answers
252 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 ...
4
votes
3answers
126 views
Largest contiguous sub-array sum
Challenge
Determine the largest contiguous sum of integers in a list.
Specifications
The first argument is a path to a file.
The file contains multiple lines.
Each line is a test case represented ...
6
votes
2answers
468 views
Obtaining a target number only using the operations ×2, ×3, and +1
Problem Introduction
You are given a primitive calculator that can perform the following
three operations with the current number x: multiply x by 2, multiply
x by 3, or add 1 to x. Your goal ...
0
votes
2answers
76 views
Code for calculating number of trailing zeroes after factorial
While trying my hands at the beginner codechef problem I came across this . So basically doing that problem with Dynamic programming is an overkill but why not try that and get some DP practice.
Nice,...
7
votes
6answers
1k views
Yet another Fibonacci number generator
First attempt at dynamic programming. I want to make this run faster and better.
fibonacci.cpp
...
4
votes
2answers
249 views
Change-making problem with specific constraints
I am a new Pythoner. I have solved a OJ project with Python. Can you tell me how can I solve it more Pythonically?
Problem Description: There are n coin denominations, each with an unlimited ...
1
vote
1answer
50 views
Simple Factor Class
I have a class which lazily factors numbers. It provides the user with these methods:
getFactors returns a ...
3
votes
2answers
117 views
Count the number of ways to obtain a sum, with consecutivity restriction
A cricketer can score 1, 2, 4 or 6 in a ball. Find in how many ways the player can score a total of "n" runs without hitting 3 consecutive boundaries. Note: Scoring 4 or 6 is considered as a boundary. ...
0
votes
0answers
69 views
Time limit exceeded for solving longest palindromic substring by dynamic programming
I have seen plenty of longest common substring search code by dynamic programming and it is an O(n^2) operation. My motivation is to solve leetcode problem longest-palindromic-substring by this ...
3
votes
1answer
249 views
Number of unique sequences of 3 digits, given a length is equal to sum
This is the "Minion's bored game" problem from Google's "Foobar challenge":
There you have it. Yet another pointless "bored" game created by the bored minions of Professor Boolean.
The game is ...
2
votes
1answer
77 views
Longest Increasing Sub-Sequence using Dynamic Programming in Python
I wrote the following function to find the longest increasing sub-sequence in an array (tuple, it doesn't work for a list since a list is mutable and it stores the results in a dictionary.). It uses ...
2
votes
0answers
81 views
Shortest bitonic tour
This a solution to the shortest bitonic tour using dynamic programming. Bitonic tour starts at the leftmost point then goes strictly rightward to the rightmost point and finally strictly leftward to ...
4
votes
2answers
222 views
Rod-Cutting Problem using dynamic programming
I wrote the following code for solving the Rod-Cutting Problem using dynamic programming:
Rod Cutting Problem: Given a rod of length n inches and an array of prices that contains prices of all ...
1
vote
0answers
92 views
Longest palindrome subsequence
This algorithm finds the longest palindrome that is a subsequence of a given input string in \$\Theta(n^2)\$.
Example
Input: character
Output: ...
0
votes
2answers
201 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 ...
3
votes
2answers
305 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 ...
0
votes
1answer
40 views
Loading URLs via a case statement
I have the following code which loads in a URL based on the id of a user-clicked button. I'm looking to compress it down as much as possible, and make it more modular and reusable:
...
3
votes
2answers
229 views
High execution time of LCS length program in Python2
I was trying to solve the Longest Common Subsequence problem on a HackerRank exercise.
It's quite simple and straightforward, just print out the length of the LCS. I submitted this code:
...
2
votes
2answers
44 views
Find the best path amongst N random points
For an application with a graphical canvas, I want to generate N points. But then I want to link those points, and I want to find the best path through those points.
I wanted to use a dynamic ...
1
vote
1answer
326 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:
...
4
votes
2answers
127 views
Number of ways to make change for an amount
Task
Write a program that, given the amount to make change for and a list of coins prints out how many different ways you can make change from the coins to STDOUT.
My approach
The number to make ...
2
votes
1answer
52 views
Optimally allocating a resource with time-varying demand and cost
I'm working on the following DP which finds the optimal way to allocate a resource. At each time step I can either allocate (0.2 resources) at cost C or not in which case the storage is reduced by the ...
2
votes
1answer
61 views
Auto registering class registry
I built this auto registering registry to look into a package and import all modules and register any classes that are a subclass of a base class. I use it as a registry for a model's choices in ...
4
votes
1answer
474 views
Finding the longest path, avoiding obstacles in a 2D plane
The Scenario
You are given a matrix of size m x n (width x height) with m*n spots where there are a few obstacles. Spots with obstacles are marked as 1, and those without are marked as 0. You can ...
