# Tag: Dynamic Programming

## LeetCode : K Inverse Pairs Array Problem Statement Solution : One of the strong heuristics that I generally use for solving counting problems in programming is that it is most likely a dynamic programming problem and most of the cases it is true, since most such counting problems can be defined recursively. In this problem, of counting the number of k-inverse pairs in an array of size 'n' (from 1 to n) can be defined recursively. […]

## Dynamic Programming in NLP - Longest Common Subsequence In this second part of the series on my posts on Dynamic Programming in NLP, I will be showing how to solve the Longest Common Subsequence problem using DP and then use modified versions of the algorithm to find out the similarity between two strings. LCS is a common programming question asked in many technical interviews. Given two strings (sequence of words, characters etc.) S1 and S2, return the number […]

## Dynamic Programming in NLP - Skip Grams In this series of posts, I will be exploring and showing how dynamic programming technique is used in machine learning and natural language processing. Dynamic programming is very popular in programming interviews. DP technique is used mainly in problems which has optimal substructure and can be defined recursively, which means that a problem of size N can be solved by solving smaller sub-problems of size m < N. Such problems […]

## LeetCode : Cherry Pickup Problem Statement Solution : This problem is probably one of the most difficult path traversal problem, I have seen on LeetCode and I will let you know the reason why. The most faulty assumption to begin with is that, this can be solved using a greedy approach, i.e. find the maximum possible cherries during the forward traversal (0,0) to (N-1, N-1) and then find the maximum possible cherries during the […]