Ingenuity-2D-DP

This repository contains code files and resources related to 2D Dynamic Programming workshop conducted by Ingenuity at IIT Bhilai.

Problems Discussed

1. Unique Paths

   Starting from the top-left corner of an m x n grid, how many unique paths are there to the bottom-right corner if you can only move either down or right at any point in time?

   Solutions:

   1. C++
      • Tabulation
      • Combinatorics
   2. Python
      • Tabulation
      • Tabulation with Space Optimization
      • Combinatorics

2. Unique Paths II

   Same as the previous problem, but now there are obstacles in the grid. You cannot move through obstacles.

   Solutions:

   1. C++
      • Tabulation
   2. Python
      • Tabulation

3. Book Shop

   You are in a book shop which sells n books, and you have x coins. Given the prices and pages of each book, find the maximum number of pages you can buy with the given amount of coins.

   Solutions:

   1. C++
      • Tabulation
      • Tabulation with Space Optimization
   2. Python
      • Tabulation with Space Optimization

4. Super Sale

   A shop sells n items, each with a weight and a price. You are given the weight of each item and the price of each item. There are g people who want to buy items. Each person can carry own maximum weight of mw. Find the maximum price that can be obtained by selling items to these people.

   Solutions:

   1. C++
      • Tabulation

   Note:

   To submit this solution visit here.

Resources

• Slides

  PPT PDF

• Video Resources

  1. Dynamic Programming Playlist | Interview Questions | Recursion | Tabulation | Striver | C++ | Java | DSA | Placements
  2. Mastering Dynamic Programming - How to solve any interview problem (Part 1)
  3. Lecture 20: Dynamic Programming II: Text Justification, Blackjack - MIT OpenCourseWare
  4. Lecture 21: Dynamic Programming III: Parenthesization, Edit Distance, Knapsack - MIT OpenCourseWare

• Classic 2D DP Problems

1. Longest Common Subsequence
2. 0-1 Knapsack
3. Matrix Chain Multiplication
4. Coin Change - I (Optimization)
5. Coin Change - II (Counting)

• Additional Problems

1. 0-1 Knapsack variants
   • ICPC : Super Sale (Same as 0-1 Knapsack)
   • CodeForces : Double KnapSack (2 knapsacks)
   • Kattis : Restaurant Orders (Simple Variant; print solutions)
2. DP on strings
   • Edit Distance (Similar to LCS)
   • Longest Palindromic Subsequence
3. CSES Problemset DP (Many variants of DP ranging from easy to hard)