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
2
votes
1answer
786 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 ...
0
votes
1answer
173 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 ...
3
votes
0answers
50 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. ...
9
votes
2answers
498 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 ...
1
vote
2answers
76 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://...
3
votes
1answer
308 views

Path Finding using Dynamic Programming

I was trying to implement a dp + graph problem. After completing the solution I tried to compare it with solution in tutorial to figure out which one was better and to find a way to improve mine if I ...
2
votes
1answer
435 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). ...
7
votes
2answers
511 views

Recursive function and memorization to find minimum operations to transform n to 1

I'm a new, self-taught programmer working on the Google FooBar challenge. I've submitted my answer (code at bottom) and it was accepted, but I'd like suggestions on how to improve my solution. ...
5
votes
3answers
1k views

Maximum path sum in a triangle with prime number check

I was given this algorithm task: You will have a triangle input below and you need to find the maximum sum of the numbers according to given rules below; You will start from the top and move ...
1
vote
2answers
772 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 ...
0
votes
1answer
155 views

Using dynamic to avoid code duplication when wrapping an API

I am dealing with 3 different types of cameras from the same manufacturer and want to write a wrapper for their API. The API structure is like this: Camera1 and Camera2 use the class ...
2
votes
0answers
602 views

Hackerrank: Max Score

Problem statement Consider an n-element sequence of integers, A = {a0, a0, ..., an-1}. We want to perform \$n\$ operations on \$A\$, where each operation is defined by the following sequence of ...
6
votes
1answer
1k views

Longest common subsequence length and backtracking the string

Problem: Given two sequences, print the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “...
4
votes
2answers
510 views

Find the longest rectilinear path in a matrix with descending entries

Problem (Skiing): Each number represents the elevation of that area of the mountain. From each area (i.e. box) in the grid, you can go north, south, east, west - but only if the elevation ...
6
votes
2answers
1k views

Length of longest palindrome subsequence

I had an interview, where I was asked to solve to this question: Given an string str, find the maximum length of palindrome subsequence. Example: >if str = 'abcda': maximum_length = 3 '...
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 ...
4
votes
1answer
959 views

Find the maximum profit if given an array of daily stock prices and allowed to buy and sell twice

I am wondering about the correctness of this method: We are given a function / algorithm findMaxProfit() that can find the maximum profit when given an array of ...
2
votes
1answer
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 - ...
4
votes
1answer
150 views

Counting increasing subsequences with a “hacker's” Binary Index Tree

This is an \$O(n \sqrt n)\$ solution to the the following problem: Given a sequence, compute the number of non-empty increasing subsequences The algorithm is to compute ...
1
vote
1answer
135 views

Find the minimum number of operations to convert 1 into n, and print the sequence of numbers

Here is my solution for the following task: Given an integer n, print the minimum number of operations needed to obtain the number n starting from the number 1, and the sequence of numbers towards the ...
3
votes
2answers
270 views

Solution to Google Code Jam 2008 round 1C problem B

This is my solution to Google Code Jam 2008 round 1C problem B (Ugly Numbers). I think it's very elegant. However, I wonder if it's too concise. What could I improve here? The problem: Once upon a ...
3
votes
2answers
142 views

UVA 100: “The 3n + 1 problem” take 2

This is my second attempt to solve this problem, my first attempt is here: UVA 100: "The 3n + 1 problem" This time I tried to take lessons from the failures and mistakes You pointed out in ...
3
votes
1answer
942 views

Finding the max product of a 2D array

Given a 2D array of unsigned integers and a maximum length n, find a path in that matrix that is not longer than n and which maximizes the product of the elements in the path. The output should ...
3
votes
1answer
396 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. ...
4
votes
1answer
658 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,...
3
votes
0answers
362 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 ...
6
votes
2answers
532 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: <...
2
votes
2answers
85 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 ...
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 ...
2
votes
1answer
444 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
497 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
1answer
204 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
987 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
85 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
169 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
336 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
203 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
571 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
3k 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 ...
1
vote
0answers
83 views

SPOJ Aliens in a Train

I need to find the largest interval with a value less than a limit Lt. The data is as follows: For every test case T: Number of elements N, limit Lt N number of elements data I wrote the ...
2
votes
0answers
802 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
350 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
4answers
986 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, ...
3
votes
1answer
306 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! ...
1
vote
3answers
724 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 ...
5
votes
1answer
468 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 ...
4
votes
2answers
383 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
997 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 ...
5
votes
3answers
234 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 ...