DP

https://leetcode.com/problems/target-sum/solutions/455024/dp-is-easy-5-steps-to-think-through-dp-questions/

First i have to use recursion to the question then i have to go for memoization and then last i will go for top down approaches.

How to find the base case?

Think of the smallest valid input. 

if(n==0 || w==0) return 0

as the smallest n would be 0 and also the weight for 0/1 knapsack would be 0 as well, we can not take negative weight on a bag. if i go to a store and the store has all the bigger items then i can not hold it to the bag so weight would be 0. similarly if the store has no item so n=0

Recursive function:

fn (i/p)

fn(smaller i/p)

if the input is n then we have to go for (n-1) as the smaller input as that will work as recursion.

 

0/1 Knapsack Problem:

 

Unbounded Knapsack Problem:

  • Bounded Knapsack Problem:

  • Other Related Problems:

  • 1D DP: "Climbing Stairs", "House Robber", "Longest Increasing Subsequence".
  • 2D DP: "Unique Paths", "Edit Distance", "Longest Common Subsequence".
  • Tree DP: "Binary Tree Maximum Path Sum", "House Robber III".
  • Interval DP: "Burst Balloons", "Palindrome Partitioning II".
  • Bitmask DP: "Traveling Salesman Problem", "Count Numbers with Unique Digits".
    •  



    Comments

    Post a Comment

    Popular posts from this blog

    c# .net learning From 19 Sep 2023

    Introduction | C# | Tutorial 1 - YouTube This is the best youtuber! Getting started with c# .net by watching video tutorial of Mr. Bangar Raju and Codewith harry: (1) Mr. Bangar Raju: (1) Working with Visual Studio .NET | C#.NET Tutorial | Mr. Bangar Raju - YouTube   (1) Working with Visual Studio .NET | C#.NET Tutorial | Mr. Bangar Raju - YouTube (2) Codewith harry: https://youtu.be/SuLiu5AK9Ps?t=296 (3) Programming with Mosh: (1) C# Tutorial For Beginners - Learn C# Basics in 1 Hour - YouTube Important topics in c#:  1. Generics  2. garbage collection  3. Exception handling  4. Interface Implementation  5. Delegates(callbacks, multicast etc)  6. Events  7. Multithreading using TPL My .NET Developer Roadmap for 2023 - YouTube Learn: RDBMS, SQL server. Fundamentals-of-Computer-Programming-with-CSharp-Nakov-eBook-v2013.pdf
    Read more

    template

     **** Combinatorics **** const ll M = 1e9+7;  // default modulus // --- Basic modular operations --- ll mod(ll x, ll m = M){      return ((x % m) + m) % m;  } ll mod_add(ll a, ll b, ll m = M){      return (a + b) % m;  } ll mod_sub(ll a, ll b, ll m = M){      return ((a - b) % m + m) % m;  } ll mod_mul(ll a, ll b, ll m = M){     return ((a % m) * (b % m)) % m; // safe for small numbers } ll mod_pow(ll a, ll b, ll m = M) {     ll res = 1;     a %= m;     while(b) {         if(b & 1) res = (res * a) % m;         a = (a * a) % m;         b >>= 1;     }     return res; } // --- Modular inverse for prime modulus --- // Fermat's Little Theorem: a^(m-2) ≡ a^(-1) (mod m) ll mod_inv_prime(ll a, ll m = M){     return mod_pow(a, m - 2, m); } // --- Modular inverse for non-prime modulus --- /...
    Read more

    settings.json

     {     "editor.fontFamily": "'Fira Code', Consolas, monospace",     "editor.fontLigatures": true,     "editor.fontWeight": "normal",     "editor.fontSize": 18,     "editor.lineHeight": 26,     "editor.wordWrap": "on",     "editor.cursorBlinking": "smooth",     "editor.cursorStyle": "underline",     "editor.cursorWidth": 5,     "editor.cursorSmoothCaretAnimation": "off",     "editor.smoothScrolling": false,     "editor.mouseWheelSmoothScroll": false,     "workbench.reduceMotion": "on",     "editor.scrollBeyondLastLine": false,     "editor.scrollBeyondLastColumn": false,     "editor.fastScrollSensitivity": 20,     "editor.allowVariableLineHeights": false,     "files.autoSave": "onFocusChange",     "explorer.confirmDelet...
    Read more