This repository is a collection of various dynamic programming problems and their solutions, showcasing the use of this powerful technique in solving complex algorithmic challenges. The problems range from optimization tasks like the Knapsack problem to combinatorial problems such as the Longest Increasing Subsequence, as well as matrix and string manipulation problems.
-
Coin Change Problem
- A classic problem dealing with finding the minimum number of coins that make a given value from a set of coin denominations.
- Go to Coin Change Problem
-
Coin Change 2 Problem
- An extension of the Coin Change problem, it involves finding the number of ways to make change for a particular amount with a given set of coins.
- Go to Coin Change 2 Problem
-
0/1 Knapsack Problem
- This problem involves selecting items with given weights and values to maximize the total value without exceeding a weight limit.
- Go to 0/1 Knapsack Problem
-
Longest Increasing Subsequence
- This repository contains solutions to find the length of the longest subsequence of a given sequence in which all elements are sorted in increasing order.
- Go to Longest Increasing Subsequence
-
Longest Increasing Path in a Matrix
- A problem that involves finding the longest increasing path through a matrix.
- Go to Longest Increasing Path in a Matrix
-
Minimum Difficulty of a Job Schedule
- This challenge focuses on finding the minimum difficulty of scheduling jobs over a number of days.
- Go to Minimum Difficulty of a Job Schedule
-
Palindrome Partitioning II
- An advanced string manipulation problem that involves finding the minimum number of cuts needed to partition a string such that every substring is a palindrome.
- Go to Palindrome Partitioning II
Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable in various domains such as optimization, combinatorics, graph algorithms, and more. This repository provides examples of dynamic programming applied to different types of problems, illustrating its versatility and efficiency.
- Solutions to a variety of dynamic programming problems.
- Detailed explanation of the algorithms and their implementation.
- Code examples in C++ showcasing efficient problem-solving techniques.
Each subdirectory in this repository is a separate project with its own README.md
file, providing detailed descriptions of the problem, the algorithm, and instructions on how to compile and run the code.
To compile and run the C++ programs in this repository, you will need a C++ compiler. Most systems come with a pre-installed C++ compiler, or you can download one such as GCC or Clang.