Skip to content

Latest commit

 

History

History

DP_striver

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
0_1_knapsack.cpp
0_1_knapsack.cpp
 
 
Fibonacci_num.cpp
Fibonacci_num.cpp
 
 
LCS.cpp
LCS.cpp
 
 
LCSubstr.cpp
LCSubstr.cpp
 
 
LIS.cpp
LIS.cpp
 
 
LIS2.cpp
LIS2.cpp
 
 
LPalS.cpp
LPalS.cpp
 
 
LRS.cpp
LRS.cpp
 
 
best_time_to_buy_stock.cpp
best_time_to_buy_stock.cpp
 
 
best_time_to_buy_stock2.cpp
best_time_to_buy_stock2.cpp
 
 
best_time_to_buy_stock3.cpp
best_time_to_buy_stock3.cpp
 
 
best_time_to_buy_stock4.cpp
best_time_to_buy_stock4.cpp
 
 
best_time_to_buy_stock5.cpp
best_time_to_buy_stock5.cpp
 
 
best_time_to_buy_stock6.cpp
best_time_to_buy_stock6.cpp
 
 
climbing_stairs.cpp
climbing_stairs.cpp
 
 
coin_change2.cpp
coin_change2.cpp
 
 
count_subset_sum_eq_to_K.cpp
count_subset_sum_eq_to_K.cpp
 
 
frog_jump.cpp
frog_jump.cpp
 
 
grid_unique_paths.cpp
grid_unique_paths.cpp
 
 
house_robber.cpp
house_robber.cpp
 
 
house_robber2.cpp
house_robber2.cpp
 
 
interleaved_str.cpp
interleaved_str.cpp
 
 
lbs.cpp
lbs.cpp
 
 
max_len_pairs.cpp
max_len_pairs.cpp
 
 
maxi_sum_subseq.cpp
maxi_sum_subseq.cpp
 
 
min_deletions_to_sort.cpp
min_deletions_to_sort.cpp
 
 
min_path_sum.cpp
min_path_sum.cpp
 
 
minimum_coins.cpp
minimum_coins.cpp
 
 
ninja_training.cpp
ninja_training.cpp
 
 
partition_equal_subset_sum.cpp
partition_equal_subset_sum.cpp
 
 
partition_given_diff.cpp
partition_given_diff.cpp
 
 
partition_min_subset_sum_diff.cpp
partition_min_subset_sum_diff.cpp
 
 
permutation_sum.cpp
permutation_sum.cpp
 
 
readme.md
readme.md
 
 
rod_cutting_problem.cpp
rod_cutting_problem.cpp
 
 
string_subseq.cpp
string_subseq.cpp
 
 
subset_sum_eq_to_K.cpp
subset_sum_eq_to_K.cpp
 
 
target_sum.cpp
target_sum.cpp
 
 
unbounded_knapsack.cpp
unbounded_knapsack.cpp
 
 
unique_paths_two.cpp
unique_paths_two.cpp
 
 

readme.md

Problems on DP

DP on Grids/2D matrices

DP on Subsequences/Subsets and target

Classic Problems

DP on strings

DP on stocks: Best time to buy and sell stocks

DP on LIS

Misc

Notes/Ptrs

How do you know it's a DP problem?

  • counting no of ways
  • minimum or maximum op in case of multiple ways
  • whenever concept of try all possible ways

Tips for developing recurrence relation

  • try to represent the problem in terms of index
  • do all possible stuffs on that index according to PS
  • if question says count all ways:
    • sum up all stuffs
  • else if question says find min
    • take min(all stuffs)