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
6
votes
1answer
466 views

Printing bowTie pattern in efficient and pythonic way

I've posted code/library to GitHub for first time over here. The code is pretty simple. It generates a BowTie pattern of given size and characters. I did attempt to implement DP by calculating only ...
4
votes
1answer
627 views

Count ways to reach the n’th stair

I have solved Leetcode climbing-stairs problem which is stated as: There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a ...
1
vote
0answers
126 views

x as the sum of unique integers raised to power n

I've done this problem using recursion. But I'm not sure that could this be optimized for bigger values of x using memoization. ...
1
vote
1answer
661 views

Compute the number of ways a given amount (cents) can be changed

Given an infinite number of different coin types (such as pennies, nickels, dimes, quarters) find out how many ways n cents can be represented. My code appears to work (although I am curious to ...
3
votes
1answer
293 views

Counting subsets with sum not exceeding some limit

I am facing a variation of a subset sum problem. I have to count the number of subsets with sum less than or equal to some integer(limit). I think the optimal solution for this problem would be the ...
2
votes
1answer
369 views

HackerRank Equal with Scala

For studying Scala, I wrote some code to solve the Equal problem on HackerRank. But I am stuck on test case #15 due to timeout. Christy is interning at HackerRank. One day she has to distribute ...
1
vote
1answer
85 views

Largest divisible subset optimization

So this is my solution to the following leetcode problem: https://leetcode.com/problems/largest-divisible-subset/description/ How could I optimize this code? I think the run time is \$\mathcal{O}(n^2)...
7
votes
1answer
201 views

Dynamic Programming with Project Euler problem 67

I am a beginner with python and programming in general. I started teaching myself about 2 months ago. I've been working my way through Project Euler and a few similar sites to build my chops, and ...
-3
votes
1answer
2k views

Counting the number of ways to break an amount into coins

I have an algorithm here that counts the number of ways that n cents can be represented using the following denominations: quarter: 25 cents dime: 10 cents nickel: 5 cents pennies: 1 cent There are ...
2
votes
1answer
768 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 ...
0
votes
1answer
212 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 ...
2
votes
1answer
910 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
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. ...
3
votes
1answer
417 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
442 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
562 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. ...
1
vote
2answers
77 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://...
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 ...
2
votes
0answers
658 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 ...
0
votes
1answer
158 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 ...
6
votes
1answer
2k 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, “...
5
votes
1answer
320 views

Hackerrank - Maximum Disjoint Subtree Product

Problem statement We define an unrooted tree, T, with the following properties: T is a connected graph with nodes ...
6
votes
2answers
2k 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 'aca' How ...
4
votes
1answer
1k 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 ...
4
votes
1answer
1k views

Student Attendance Record II

I'm currently working on the Student Attendance Record II problem: Given a positive integer \$n\$, return the number of all possible attendance records with length \$n\$, which will be regarded ...
4
votes
2answers
564 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 ...
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
151 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
148 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
307 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
1answer
1k 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 ...
4
votes
1answer
432 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. ...
3
votes
2answers
145 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 ...
4
votes
1answer
778 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
89 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
580 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
216 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
1k 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
468 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
594 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
88 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
184 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
353 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 in ...
1
vote
2answers
227 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
682 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 ...
2
votes
0answers
1k 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 (...
4
votes
1answer
396 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
549 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 ...