Dynamic Programming Problems Repository

Released: 29 May, 2024

Written by Ayush Aryan.

(C) Copyright 2024-2025, by Ayush Aryan . All rights reserved.

Please address all contributions, suggestions, and inquiries to the user mailing list

This repository contains solutions to various dynamic programming problems implemented in C++. Each file is named according to the problem it solves for easy identification and navigation.

Table of Contents

• 0/1 Knapsack Problem
• Coin Change Problem
• Longest Common Subsequence (LCS)
• Matrix Chain Multiplication
• Sub-Set Sum Problem

Problems and Solutions

0/1 Knapsack Problem

• File Name: 0|1 Knapsack problem
• Description: Solution to the classic 0/1 Knapsack problem where we determine the maximum value that can be obtained by selecting items without exceeding the weight capacity of the knapsack.

Coin Change Problem

• File Name: Coin Change
• Description: Implementation of the coin change problem which finds the minimum number of coins required to make a certain amount using the given denominations.

Longest Common Subsequence (LCS)

• File Name: LCS
• Description: Algorithm to find the length of the longest common subsequence between two sequences.

Matrix Chain Multiplication

• File Name: Matrix Chain Multiplication
• Description: Solution to the matrix chain multiplication problem that determines the most efficient way to multiply a given sequence of matrices.

Sub-Set Sum Problem

• File Name: Sub-Set Sum
• Description: Solution to the subset sum problem where we check if there exists a subset of the given set with a sum equal to a given target.

History

• 0/1 Knapsack Problem: Rename 10.cpp to 0|1 Knapsack problem (3 minutes ago)
• Coin Change: Rename 17.cpp to Coin Change (1 minute ago)
• LCS: Rename length common subsequence (LCS) to LCS (2 minutes ago)
• Matrix Chain Multiplication: Rename 12.cpp to Matrix Chain Multiplication (1 minute ago)
• Sub-Set Sum: Update and rename 18.cpp to Sub-Set Sum (now)

Repository Navigation

This repository is organized by problem type, with each solution in its respective file. Explore the files and their contents to understand the implementation of various dynamic programming problems.

---

Help people interested in this repository understand your project by exploring the README and the provided problem solutions.