GitHub - Jeffrin2005/Dynamic_Programming: DP Problems

Branches Tags

Name		Name	Last commit message	Last commit date
Latest commit History 222 Commits
.vscode		.vscode
class Solution { public: int minDistance(string s1, string s2) { int n=s1.size(); int m=s2.size(); s1 = '#' + s1; s2 = '#' + s2; vector<vector<int>>dp(n+1,vector<int>(m+1,0)); dp[0][0] = 0; for(int i=1;i<=n;i++) dp[i][0]=i; for(int j=1;j<=m;j++) dp[0][j]=j; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(s1[i]==s2[j]) dp[i][j] = 0 + dp[i-1][j-1];		class Solution { public: int minDistance(string s1, string s2) { int n=s1.size(); int m=s2.size(); s1 = '#' + s1; s2 = '#' + s2; vector<vector<int>>dp(n+1,vector<int>(m+1,0)); dp[0][0] = 0; for(int i=1;i<=n;i++) dp[i][0]=i; for(int j=1;j<=m;j++) dp[0][j]=j; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(s1[i]==s2[j]) dp[i][j] = 0 + dp[i-1][j-1];
(DP)Longest Unequal Adjacent Groups Subsequence I.cpp		(DP)Longest Unequal Adjacent Groups Subsequence I.cpp
(DP_TABULATION)Maximum Subarray.cpp		(DP_TABULATION)Maximum Subarray.cpp
(RECUR + MEMO) Divisor Game.cpp		(RECUR + MEMO) Divisor Game.cpp
(RECUR + MEMO)Pascal's Triangle II.cpp		(RECUR + MEMO)Pascal's Triangle II.cpp
(RECUR + MEMO)Pascal's Triangle.cpp		(RECUR + MEMO)Pascal's Triangle.cpp
(RECUR + TABU)Is Subsequence.cpp		(RECUR + TABU)Is Subsequence.cpp
(RECURION + MEMO + TABULATIN)Best Time to Buy and Sell Stock.cpp		(RECURION + MEMO + TABULATIN)Best Time to Buy and Sell Stock.cpp
(RECURIVE)Counting Bits.cpp		(RECURIVE)Counting Bits.cpp
(RECURSION)Longest Palindromic Substring.cpp		(RECURSION)Longest Palindromic Substring.cpp
(RECURSION)Min Cost Climbing Stairs.cpp		(RECURSION)Min Cost Climbing Stairs.cpp
(RECURSION)Subset Sums.cpp		(RECURSION)Subset Sums.cpp
(RECURSIVE)Combination Sum II.cpp		(RECURSIVE)Combination Sum II.cpp
(RECURSIVE)N-th Tribonacci Number.cpp		(RECURSIVE)N-th Tribonacci Number.cpp
(TABLUATION)Pascal's Triangle II.cpp		(TABLUATION)Pascal's Triangle II.cpp
(TABULATION)Counting Bits.cpp		(TABULATION)Counting Bits.cpp
(TABULATION)Divisor Game.cpp		(TABULATION)Divisor Game.cpp
(TABULATION)N-th Tribonacci Number.cpp		(TABULATION)N-th Tribonacci Number.cpp
(TABULATION)Pascal's Triangle.cpp		(TABULATION)Pascal's Triangle.cpp
. Count Sorted Vowel Strings.cpp		. Count Sorted Vowel Strings.cpp
9RECUR + MEMO)Fibonacci Number.cpp		9RECUR + MEMO)Fibonacci Number.cpp
Arithmetic Slices.cpp		Arithmetic Slices.cpp
Best Sightseeing Pair.cpp		Best Sightseeing Pair.cpp
Best Time to Buy and Sell Stock II.cpp		Best Time to Buy and Sell Stock II.cpp
Best Time to Buy and Sell Stock with Cooldown.cpp		Best Time to Buy and Sell Stock with Cooldown.cpp
Best Time to Buy and Sell Stock with Transaction Fee.cpp		Best Time to Buy and Sell Stock with Transaction Fee.cpp
Best Time to Buy and Sell Stock(BRUTE + MEMO).cpp		Best Time to Buy and Sell Stock(BRUTE + MEMO).cpp
Best Time to Buy and Sell Stock(RECUR + MEMO).cpp		Best Time to Buy and Sell Stock(RECUR + MEMO).cpp
C - Theofanis' Nightmare .cxx		C - Theofanis' Nightmare .cxx
C1. Magnitude (Easy Version).cpp		C1. Magnitude (Easy Version).cpp
Climbing Stairs(RECU + MEMO).cpp		Climbing Stairs(RECU + MEMO).cpp
Climbing Stairs.cpp		Climbing Stairs.cpp
Codeforces._NeW.c		Codeforces._NeW.c
Count Number of Teams.cpp		Count Number of Teams.cpp
Count Numbers with Unique Digits.cpp		Count Numbers with Unique Digits.cpp
Count Sorted Vowel Strings..cpp		Count Sorted Vowel Strings..cpp
Count Sorted Vowel Strings.cpp		Count Sorted Vowel Strings.cpp
Count Square Submatrices with All Ones.cpp		Count Square Submatrices with All Ones.cpp
Count Substrings That Differ by One Character.cpp		Count Substrings That Differ by One Character.cpp
CountSubsetswithSumK.cpp		CountSubsetswithSumK.cpp
Cppp.cxx		Cppp.cxx
Cut Ribbon(CF).cpp		Cut Ribbon(CF).cpp
Decode Ways.cpp		Decode Ways.cpp
Delete and Earn.cpp		Delete and Earn.cpp
DeleteOperationforTwoStrings.cpp		DeleteOperationforTwoStrings.cpp
Distinct Subsequences.cpp		Distinct Subsequences.cpp
Edit Distance.cpp		Edit Distance.cpp
Egg Drop With 2 Eggs and N Floors.cpp		Egg Drop With 2 Eggs and N Floors.cpp
Fibonacci Number.cpp		Fibonacci Number.cpp
Flip String to Monotone Increasing.cpp		Flip String to Monotone Increasing.cpp
Generate Parentheses.cpp		Generate Parentheses.cpp
House Robber.cpp		House Robber.cpp
Integer Break.cpp		Integer Break.cpp
Integer Replacement.cpp		Integer Replacement.cpp
Is Subsequence.cpp		Is Subsequence.cpp
Jump Game.cpp		Jump Game.cpp
LSWR.cxx		LSWR.cxx
Largest Divisible Subset.cpp		Largest Divisible Subset.cpp
Last Stone Weight II.cpp		Last Stone Weight II.cpp
Longest Binary Subsequence Less Than or Equal to K.cpp		Longest Binary Subsequence Less Than or Equal to K.cpp
Longest Bitonic Sequence.cpp		Longest Bitonic Sequence.cpp
Longest Increasing Subsequence.cpp		Longest Increasing Subsequence.cpp
Longest String Chain.cpp		Longest String Chain.cpp
Longest Subarray of After Deleting One Element.cpp		Longest Subarray of After Deleting One Element.cpp
Longest Subarray of 1's After Deleting One Element.cpp		Longest Subarray of 1's After Deleting One Element.cpp
Longest Unequal Adjacent Groups Subsequence I.cpp		Longest Unequal Adjacent Groups Subsequence I.cpp
LongestCommonSubsequence.cpp		LongestCommonSubsequence.cpp
LongestCommonSubstring.cpp		LongestCommonSubstring.cpp
LongestPalindromicSubsequence.cxx		LongestPalindromicSubsequence.cxx
Maximum Absolute Sum of Any Subarray.cpp		Maximum Absolute Sum of Any Subarray.cpp
Maximum Alternating Subsequence Sum.cpp		Maximum Alternating Subsequence Sum.cpp
Maximum Difference Score in a Grid.cpp		Maximum Difference Score in a Grid.cpp
Maximum Length of Repeated Subarray.cpp		Maximum Length of Repeated Subarray.cpp
Maximum Number of Operations With the Same Score II.cpp		Maximum Number of Operations With the Same Score II.cpp
Maximum Product Subarray.cpp		Maximum Product Subarray.cpp
Maximum Repeating Substring.cpp		Maximum Repeating Substring.cpp
Maximum Sum of Two Non-Overlapping Subarrays.cpp		Maximum Sum of Two Non-Overlapping Subarrays.cpp
Min Cost Climbing Stairs.cpp		Min Cost Climbing Stairs.cpp
Minimu.cpp		Minimu.cpp
Minimum Cost For Tickets.cpp		Minimum Cost For Tickets.cpp
Minimum Deletions to Make String Balanced.cpp		Minimum Deletions to Make String Balanced.cpp
Minimum Falling Path Sum.cpp		Minimum Falling Path Sum.cpp
Minimum Number of Operations to Make X and Y Equal.cpp		Minimum Number of Operations to Make X and Y Equal.cpp
Minimum Time to Make Rope Colorful(RECURSION).cpp		Minimum Time to Make Rope Colorful(RECURSION).cpp
Minimum Time to Make Rope Colorful(TABULATION).cpp		Minimum Time to Make Rope Colorful(TABULATION).cpp
MinimumInsertionStepstoMakeaStringPalindrome.cpp		MinimumInsertionStepstoMakeaStringPalindrome.cpp
Minimum_Falling_Path_Sum.cpp		Minimum_Falling_Path_Sum.cpp
Minimum_Path_Sum.cpp		Minimum_Path_Sum.cpp
Money Buys Happiness(CF).cpp		Money Buys Happiness(CF).cpp
Mortal Kombat Tower,.cxx		Mortal Kombat Tower,.cxx
N-th Tribonacci Number.cpp		N-th Tribonacci Number.cpp
Nth Tribonacci Number.cpp		Nth Tribonacci Number.cpp
Number of Dice Rolls With Target Sum.cpp		Number of Dice Rolls With Target Sum.cpp
Number of Good Ways to Split a String(Recursion).cpp		Number of Good Ways to Split a String(Recursion).cpp
Number of Longest Increasing Subsequence.cpp		Number of Longest Increasing Subsequence.cpp
Number of Smooth Descent Periods of a Stock.cpp		Number of Smooth Descent Periods of a Stock.cpp
Palindrome Partitioning.cpp		Palindrome Partitioning.cpp
Palindromic Substrings.cpp		Palindromic Substrings.cpp
Partition Array for Maximum Sum.cpp		Partition Array for Maximum Sum.cpp