Questions tagged [dynamic-programming]

Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.

Filter by
Sorted by
Tagged with
4
votes
1answer
578 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
83 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
487 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
198 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
908 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
323 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 ...
4
votes
1answer
469 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 ...
3
votes
0answers
83 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
163 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
313 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
94 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
186 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
500 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 ...
1
vote
0answers
2k 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 ...
2
votes
0answers
670 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
337 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. ...
9
votes
2answers
434 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 undershoot of the line length, cubed ...
3
votes
1answer
300 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! ...
7
votes
4answers
882 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, ...
2
votes
1answer
419 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 ...
5
votes
1answer
415 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
676 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
365 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
978 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 ...
6
votes
1answer
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 ...
5
votes
3answers
220 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
2k 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
402 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
2k views

Yet another Fibonacci number generator

First attempt at dynamic programming. I want to make this run faster and better. fibonacci.cpp ...
5
votes
2answers
958 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
250 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
145 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. ...
3
votes
1answer
319 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
460 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
305 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
1k 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
294 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
341 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 ...
2
votes
2answers
2k 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
43 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: ...
5
votes
2answers
728 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
73 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
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: ...
5
votes
2answers
363 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
82 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
817 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 ...
5
votes
1answer
2k 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 ...
0
votes
1answer
812 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
1answer
172 views

0-1 Knapsack in Java

I'm looking for advice on coding practices in general. ...
4
votes
5answers
752 views

Pass Triangle challenge

In order to solve this challenge: Challenge Description By starting at the top of the triangle and moving to adjacent numbers on the row below, the maximum total from top to bottom is 27. <...