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
3
votes
3answers
443 views

Find maximum value of recursively-defined "fusc" function

I've been trying this question from SPOJ, which asks for the user to enter a number n, and they will receive a maximum fusc value that lies in between 0 to ...
2
votes
1answer
65 views

Divide array into three disjoint sets with equal sum

Problem definition : Array partition problem Given an array of positive integers, divide it into three disjoint subsets having equal sum. These disjoint sets cover the complete array. Example Input: [...
1
vote
1answer
66 views

Target Sum array using Dynamic Programming

I'm learning Dynamic Programming and trying to solve this Target Sum array problem. I've to find an array of integers that sums to a given target sum using the integers of given input array. I've used ...
3
votes
1answer
145 views

Recursive solution of ordered Coin Combinations II (CSES)

Question Link Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using ...
2
votes
1answer
43 views

Find ALL duplicate subtrees. using recursion

This is just a practice exercise, I'm trying to understand dynamic programming as deeply as I can. I solved this using recursion, though I am not sure if it will always work. If anyone could tell me a ...
0
votes
0answers
60 views

Better Approach for the House Robbery Problem (LeetCode 198)?

The problem states that you have to rob the maximum money stashed in the houses but you cannot rob two adjacent houses. array[i] denotes the money in the (i)th house. I got the following code ...
1
vote
2answers
113 views
1
vote
1answer
582 views

Patch a JSON object using dynamic / ExpandoObject with System.Text.Json

Background Recently, I was making some updates to an "older" library that would handle PATCH-style modifications to an object that is persisted in a JSON format on our document-storage ...
0
votes
3answers
199 views

Calculate sum of a substring

I try to solve some old Codeforces questions. The problem is; Petya once wrote a sad love song and shared it to Vasya. The song is a string consisting of lowercase English letters. Vasya made up q ...
3
votes
1answer
141 views

Killing a Hydra - Overengineered

Background This question is inspired by the question: Killing a hydra, and my response therein. I will restate the problem at hand in full so that this question is fully self contained You can only ...
5
votes
1answer
59 views

K Inverse Pairs Array - Brute Force

For an integer array nums, an inverse pair is a pair of integers [i, j] where ...
3
votes
1answer
64 views

Haskell implementation of Needleman-Wunsch

The code below is a Haskell implementation of Needleman-Wunsch algorithm for sequence alignment (and string edit distance). It's an experiment in trying to closely imitate the dynamic programming ...
1
vote
2answers
97 views

I want reduce the time complexity for this ladder problem to find the minimum ladders required

I was trying to attempt below given challenge. I tried multiple ways to solve the problem but none of them were good enough to pass the time limit. Please advise if you have any idea to improve on ...
4
votes
2answers
68 views

Unique Paths II, dynamic programming problem, O(n^2) time, O(n^2) space

This is based on this leetcode question. I get the correct answer, but I know it could be much, much cleaner. I also know there is supposed to be an O(n) space solution, but I'm not sure how to ...
3
votes
1answer
2k views

Count the number of distinct subarrays

I want to determine the number of distinct subarrays that can form having at most a given number of odd elements. Two subarrays are distinct if they differ at even one position. The subarray is a ...
2
votes
1answer
59 views

Haskell Dynamic Programming on a Tree

Here is my shot at Homework 8 of CIS-194 (from Spring '13). The problem is about a hierarchy of employees at a company (a tree), each node being of type Employee, ...
0
votes
0answers
50 views

Efficiently calculate value of Pascal's Triangle using memoization and recursion(updated)

Follow up to Efficiently calculate value of Pascal's Triangle using memoization and recursion Based on feedback given by jvwh in the answers ...
3
votes
1answer
104 views

Efficiently calculate value of Pascal's Triangle using memoization and recursion

So reading about functional programming, applications to dynamic programming, and learning Scala. I figured I would try it out with a popular example, Pascal's Triangle, tests against known values ...
0
votes
0answers
85 views

LeetCode: Delete and Earn C#

https://leetcode.com/problems/delete-and-earn/ Given an array nums of integers, you can perform operations on the array. In each operation, you pick any nums[i] and delete it to earn nums[i] points. ...
1
vote
0answers
49 views

LeetCode: range sum query mutable c#

https://leetcode.com/problems/range-sum-query-mutable/ I am trying to solve this question using dynamic programming. I guess the guys in leetcode want to limit us to use segment tree or one of the ...
-1
votes
1answer
72 views

Grid Dynamic Programming

atcoder.jp Problem Statement: There is a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the ...
4
votes
1answer
133 views

Searching for an idiomatic Rust implementation of Minimum Edit Distance (LeetCode #72)

I am solving LeetCode Dynamic Programming challenges (this one is #72, at https://leetcode.com/problems/edit-distance). Here below, I've implemented a Rust solution for the minimum edit distance ...
0
votes
1answer
67 views

Find a sum using just two different digits

The problem statement was pretty easy and I was able to run half of the test cases, but some of the test cases in the end gave me the error of memory limit reached. What can I do here to improve the ...
1
vote
0answers
29 views

Divide a set into subset with some constraints

Note - I am not sure whether this question belongs to stackoverflow or CSE stackexchange or here Problem: Given a list Lconsisting of not necessarily unique non-...
3
votes
0answers
94 views

C++ - Longest Common Subsequence

Link to the Problem Here is my code to compute the length of the longest common subsequence of two integer arrays arr[] and brr[]...
3
votes
0answers
209 views

LeetCode: Stone Game C#

https://leetcode.com/problems/stone-game/ Alex and Lee play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones ...
1
vote
1answer
429 views

Code A Primitive Calculator ( x3,x2,+1) Using Dynamic programming [closed]

Question -You are given a primitive calculator that can perform the following three operations with the current number 𝑥: multiply 𝑥 by 2, multiply 𝑥 by 3, or add 1 to 𝑥. Your goal is given ...
0
votes
1answer
178 views

Generate unique string permutations recursively

🧩 Objective Write a recursive method for generating all permutations of an input string. Return them as a set. See: Recursive String Permutations - Interview Cake 🔎 Questions 1: How does the ...
9
votes
1answer
839 views

LeetCode on Longest Palindromic Substring in Python

This is a programming question from LeetCode: Given a string s, return the longest palindromic substring in s. Example 1: Input: s = "babad" Output: "bab" Note: "aba" is ...
2
votes
1answer
43 views

Why below recursive DP solution is so slow? (Leetcode Q# 123 - Best Time to Buy and Sell Stock III)

This is regarding leetcode Question# 123. I have solved the question (code below) but the solution is showing "Your runtime beats 5.89 % of cpp submissions."? Is there any additional ...
3
votes
0answers
221 views

Split money into every possible combination of coin denominations

Background and objective of the code Based on this Dev.to challenge, I wrote the Python code below (TIO link also available). The task was to return the least number of coins in a given denomination ...
4
votes
1answer
98 views

C++ Dynamic Array Class Testing

I'm creating a basic Dynamic Array class in C++, and I'd like to know if there are any bugs/memory leaks I haven't noticed yet. dyn_arr.h : ...
2
votes
1answer
60 views

Find sequence to a target number using restricted set of primitive operations

Given an integer 𝑛, compute the minimum number of operations(+1, x2, x3) needed to obtain the number 𝑛 starting from the number 1. I did this using this code: ...
2
votes
2answers
108 views

Knapsack performance issue

I'm solving a knapsack problem here. It works, but gives time limit exceeds on a certain test case. Problem statement There are N items, numbered 1,2,…,N. For each i (1≤i≤N), Item i has a weight of ...
0
votes
1answer
270 views

LeetCode 1320: Minimum Distance to Type a Word Using Two Fingers II

I'm posting my Python code for LeetCode's 1320. If you have time and would like to review, please do so. Problem You have a keyboard layout as shown above in the XY plane, where each English ...
1
vote
1answer
91 views

LeetCode 1320: Minimum Distance to Type a Word Using Two Fingers I

I'm posting my C++ code for LeetCode's 1320. If you have time and would like to review, please do so. Thank you! Problem You have a keyboard layout as shown above in the XY plane, where each English ...
-1
votes
1answer
205 views

LeetCode 375: Guess Number Higher or Lower II

I'm posting my C++ code for LeetCode's Guess Number Higher or Lower II. If you have time and would like to review, please do so. Problem We are playing the Guess Game. The game is as follows: I pick ...
2
votes
1answer
259 views

How can I use the State monad effectively in Haskell?

I have written a simple fibonacci function in Haskell that uses the State monad to save solutions to overlapping sub-problems. Now despite the function working I am not really happy with the solution, ...
1
vote
1answer
388 views

Maximum subset sum with no adjacent elements

Write a function that takes an array of integers (Both Positive and negative) and return the maximum sum of non adjacent elements. Note that even if all values are negative, I don't have an option to ...
1
vote
2answers
102 views

Recursive brute-force approach to maximum points you can obtain from cards

I came across this question on Leetcode. The question description is as follows: There are several cards arranged in a row, and each card has an associated number of points. The points are given in ...
2
votes
2answers
68 views

(Java) Read .txt and organize activities for hours / minutes

Doubts in logic to generate the output file according to the example I need that even if he reaches the total_min <720 condition he continues to travel the lines. 720 is the total number of minutes ...
1
vote
1answer
62 views

Matrix problem, the path that is the flattest

So in this problem I am given an NxN matrix, in which each value of the matrix represents an altitude. I need to find the best path from the top-left corner to the bottom-right one, my moves being ...
2
votes
1answer
104 views

LeetCode: Trapping Rain Water DP C#

Please review for performance and C# style. I already solved this question in 1 way. LeetCode: trapping rain water C# I tried also the dynamic programming approch https://leetcode.com/problems/...
2
votes
2answers
220 views

C# - Reapply the manipulation of JS Object in .Net Core

IMPORTANT: I made another version with some improvements: Version 2 Since some months ago I disagree with the native/code methods to manipulate dynamic or ...
2
votes
1answer
68 views

Is there a route to the end of the jump table?

I'm currently learning about Dynamic Programming and solving a "coding question" related to the topic. Given an array of non-negative integers, you are initially positioned at the first ...
3
votes
2answers
1k views

LeetCode: Longest String Chain (Java)

For the question, I had a pretty messy solution so I would like some advice on how to better use Java to make the code a bit cleaner. Also, a semi-hack that I did that I'm not proud of is checking if ...
1
vote
1answer
46 views

Dynamic SQL query for count data

I'm working on an application that counts the number of employees in each department. Here's my code: ...
3
votes
1answer
117 views

Find the smallest number of perfect squares that sum to a target

Given a positive integer n, find the smallest number of perfect squares (for example, 1, 4, 9, 16, ...) that sum to n. ...
1
vote
2answers
90 views

A function to scan user input as string

I know that multiple functions are already available. However, I thought of writing my own because I wanted to learn the logic (and also because I thought there wasn't enough confusion :P). Please ...
7
votes
1answer
778 views

Printing the number of ways a message can be decoded

My below solution to the following problem is exceeding the maximum recursion depth. I am looking for any improvements which i can make. Problem Alice and Bob need to send secret messages to each ...

1
2 3 4 5 6