Longest Common Subsequence Solution
The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to given two sequences. LCS problem is used to determine how similar the two DNA strands are.
Category: Dynamic Programming
Longest Increasing Subsequence Solution (LIS) – LeetCode Solution [Medium]
Given an integer array arr, return the length of the longest strictly increasing subsequence. Strictly increasing sequence is a sequence such that all elements of the sequence are sorted in increasing order.
Find the minimum distance to travel through a road having hills [Interview Question]
Alansh has to travel through a road having hills of different heights. Also each hill has a cave to pass through it, to avoid travelling extra distance of a hill. Alansh wants to travel through this road by taking at most K caves.
Edit Distance – LeetCode Solution [Hard]
Given two strings word1 and word2 (in lowercase alphabets), return the minimum number of operations required to convert word1 to word2.
Decode Ways – LeetCode Solution [Medium]
A message containing letters from A-Z can be encoded into numbers. To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping
Greedy approach vs Dynamic Programming
Greedy approach and Dynamic programming both are used for solving optimisation problems. However often we need to use DP since optimal solution cannot be guaranteed by a greedy algorithm.
Knapsack problem (Finding selected items)
A little recap: Let given weights & values of n items to be put in a knapsack of capacity W ie.
Knapsack Problem (Dynamic Programming)
An optimal solution to problem contain optimal solution to subproblems. To consider all subset of items, 2 cases for every item arises