Dynamic programming

https://medium.freecodecamp.org/demystifying-dynamic-programming-3efafb8d4296

https://medium.com/@zsalloum/how-to-think-in-dynamic-programming-3f6804a79429

https://people.cs.clemson.edu/~bcdean/dp_practice/

http://algorithms.tutorialhorizon.com/

http://www.geeksforgeeks.org/fundamentals-of-algorithms/#DynamicProgramming

http://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/

https://www.quora.com/What-are-the-top-10-most-popular-dynamic-programming-problems-among-interviewers

https://www.hackerearth.com/notes/dynamic-programming-problems-involving-grids/

https://www.hackerearth.com/notes/codemonk-dynamic-programming-ii-1/

https://www.hackerearth.com/notes/dynamic-programming-for-beginners-part-2-1-d/

https://tp-iiita.quora.com/Dynamic-Programming-Part-1

http://algo-visualizer.jasonpark.me/#path=dp/knapsack_problem/basic

https://medium.com/@pratikone/dynamic-programming-for-the-confused-rod-cutting-problem-588892796840#.v2elzgpfw

Memoization(top down) usually becomes more complicated to implement but it has some advantages in problems, mainly those which you do not need to compute all the values for the whole matrix to reach the answer like: LCS.

Tabulation(bottom up) is easy to implement but it may compute unnecessary values sometimes. It also has benefits of less overhead.

Fibonacci

http://www.nayuki.io/page/fast-fibonacci-algorithms

http://blog.senko.net/progressive-fibonacci

http://www.reddit.com/r/programming/comments/258fh9/so_how_do_you_actually_calculate_the_fibonacci/

Let T(n) be the time complexity to compute F(n). Then, T(n) = T(n-1) + T(n-2) + O(1). Thus T(n) = O(2^(n/2)). The program takes exponential time.

public static int DP(int n){

if(n < 2){

return n;

}

int n1 = 0;

int n2 = 1;

for(int i = 2; i <= n; i++){

int sum = n1 + n2;

n1 = n2;

n2 = sum;

}

return n2;

}

Code above has complexity O(n). But it is possible to have log(n) complexity - matrix exponentiation is most commonly used concept. Another concept is fast doubling method

https://www.hackerearth.com/notes/fast-doubling-method-to-find-nth-fibonacci-number/

https://www.nayuki.io/page/fast-fibonacci-algorithms

Fast doubling is based on two formulae

F(2n) = F(n)[2*F(n+1) – F(n)]

F(2n + 1) = F(n)² + F(n+1)²

Knapsack problem

A fixed size knapsack is defined. Every item has size and value. Maximize value of knapsack

#include <stdio.h>int max(int a, int b) { return (a > b)? a : b; }// Returns the maximum value that can be put in a knapsack of capacity Wint knapsack(int W, int wt[], int val[], int n){ int i, w; int K[n+1][W+1]; // Build table K[][] in bottom up manner for (i = 0; i <= n; i++) { for (w = 0; w <= W; w++) { if (i==0 || w==0) K[i][w] = 0; else if (wt[i-1] <= w) K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); else K[i][w] = K[i-1][w]; } } return K[n][W];}int main(){ int val[] = {60, 100, 120}; int wt[] = {10, 20, 30}; int W = 50; int n = sizeof(val)/sizeof(val[0]); printf("\nValue = %d", knapsack(W, wt, val, n)); return 0;}

Coin Change

Given infinite supply of coins of different values S={S1, S2, S3,..} and target SUM

Problem 1) minimize total number of coins

https://en.wikipedia.org/wiki/Change-making_problem

http://algorithms.tutorialhorizon.com/dynamic-programming-minimum-coin-change-problem/

https://interactivepython.org/runestone/static/pythonds/Recursion/DynamicProgramming.html

http://www.ccs.neu.edu/home/jaa/CS7800.12F/Information/Handouts/dyn_prog.pdf

Problem 2) how many ways we can make a change?

http://algorithms.tutorialhorizon.com/dynamic-programming-coin-change-problem/

https://www.youtube.com/watch?v=_fgjrs570YE

http://stackoverflow.com/questions/15859432/stackoverflowerror-for-coin-change-in-scala

http://py-algorithm.blogspot.ru/2011/04/blog-post_20.html

Сколькими способами можно разменять рубль на монеты достоинством в 1, 2, 5, 10, 20 и 50 копеек? Answer: 4562

Число способов разменять сумму a с помощью n типов монет равняется

• • числу способов разменять сумму a с помощью всех типов монет, кроме первого,плюс

  • число способов разменять сумму a − d с использованием всех n типов монет, где d — достоинство монет первого типа.

Пусть у нас есть 23 центов и мы спрашиваем, сколько способов выплатить её монетами не больше 10 центов (индекс = 2). Это количество способов складывается из двух:

- либо мы выплатим одну десятицентовую монетку, и будем считать количество способов выплатить оставшиеся 13 центов, также монетами не больше 10 центов;

- либо мы не трогаем десятицентовые, и считаем количество способов выплатить всю сумму в 23 цента меньшими монетами - т.е. не старше пятака (индекс = 1);

общее количество для 23 центов и монет не старше 10 как я уже сказал складывается из этих двух. вот у вас последняя строчка и есть сумма двух рекурсивных вызовов к той же функции либо с уменьшенным индексом максимальной монеты, либо с уменьшенной суммой.

а первые две строки определяют когда цепочка рекуррентных вызовов должна остановиться (на очевидных крайних случаях) и что она должна вернуть.

public class Coins {

private static int[] COINS_NOM = {1, 5, 10, 25, 50};

public static int getCountOfWays(int money) {

return getCountOfWays(money, 4);
}

private static int getCountOfWays(int money, int indexOfCoin) {

if (money < 0 || indexOfCoin < 0) return 0;

if (money == 0 || indexOfCoin == 0) return 1;

return getCountOfWays(money, indexOfCoin - 1) + getCountOfWays(money - COINS_NOM[indexOfCoin], indexOfCoin);

}

}

Python

def countChange(amount): return cc(amount, 5)

def cc(amount, kindsOfCoins):
if amount==0: return 1
if amount<0 or kindsOfCoins==0: return 0
else: return cc(amount, kindsOfCoins-1)+ cc(amount-firstDenomination(kindsOfCoins), kindsOfCoins)

def firstDenomination(kindsOfCoins):
if kindsOfCoins==1: return 1 #1 цент
elif kindsOfCoins==2: return 5 #5 центов
elif kindsOfCoins==3: return 10 #10 центов
elif kindsOfCoins==4: return 25 #25 центов
else: return 50 #50 центов

Stairs climbing
http://algorithms.tutorialhorizon.com/dynamic-programming-stairs-climbing-puzzle/

Stairs has n steps. Person can jump 1,2 or 3 steps at a time.

How many possible ways exists to climb?

At every step there are 3 possible jumps, hence

Answer(n) = Answer(n-1) + Answer(n-2) + Answer(n-3) +1

We can store solution for sub-problem in array and use memoization

int countWays(int n){

int memo[]=new int[n+1]

Arrays.fill(memo,-1)

return helper(n, memo)

}

int helper(int n, int[] memo){

if n<0 return 0

if n=1 return 1

if memo[n] > -1 return memo[n]

memo[n] = helper(n-1, memo) + helper(n-2, memo) + helper(n-3, memo)

return memo

}

Edit distance

https://algorithmstuff.wordpress.com/2014/03/17/edit-distance/

https://xlinux.nist.gov/dads/HTML/Levenshtein.html

http://julesjacobs.github.io/2015/06/17/disqus-levenshtein-simple-and-fast.html

int minDistance(String word1, String word2) {

int dp[][] = new int[word1.length() + 1][word2.length() + 1];

for(int i = 0; i <= word1.length(); ++i)

for(int j = 0; j <= word2.length(); ++j)

dp[i][j] = -1;

return getDistance(word1, word2, word1.length(), word2.length(), dp);

}

int getDistance(String word1, String word2, int i, int j, int [][]dp) {

if(i == 0) return j;

if(j == 0) return i;

if(dp[i][j] >= 0) return dp[i][j];

if(word1.charAt(i - 1) == word2.charAt(j - 1))

return dp[i][j] = getDistance(word1, word2, i - 1, j - 1, dp);

else

return dp[i][j] = 1 + Math.min(getDistance(word1, word2, i - 1, j - 1, dp),

Math.min(

getDistance(word1, word2, i - 1, j, dp),

getDistance(word1, word2, i, j - 1, dp)));

}

longest common subsequence

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

http://www.codeproject.com/Articles/11537/The-Longest-Common-Substring-with-Maximal-Consecut

Board traversal

Starting in the top left corner of grid (m*n), how many routes (without backtracking) exists to the bottom right corner.

We need to make M horizontal and N vertical moves in any order. How many permutations are possible? It is C(n+m,n) = (m+n)!/(m!*n!)

recursive code below take exponential time:

int ROWS=10; int COLS=20;

int count( int[][]matrix, int row, int col){

if (row = ROWS || col == COLS) return 1;

return count(matrix, row+1, col) + count(matrix, row, col+1)

}

DP stores intermediate values in array:

http://algorithms.tutorialhorizon.com/dynamic-programming-count-all-paths-from-top-left-to-bottom-right-of-a-mxn-matrix/

Matrix

https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/LongestIncreasingPath.java

Minimum cost board traversal

http://algorithms.tutorialhorizon.com/dynamic-programming-minimum-cost-path-problem/

Its a DP problem.

F(i,j) = Min (F(i-1,j), F(i-1,j-1), F(i,j-1)) if (diagonal move allowed

Cre­ate a solu­tion matrix of the same size as given matrix.We will fill this matrix in Bottom-up manner. At every cell, we have two options (go right or down) and we will choose the minimum of these two. So for any i,j cell

solution[i][j] = A[0][j] if i=0 , first row = A[i][0] if j=0, first column = A[i][j] + Min(solution[i-1],[j] , solution[i][j-1]) if i>0 && j>0

python:

mat = [

[ 1, 7, 9, 2 ],

[ 8, 6, 3, 2 ],

[ 1, 6, 7, 8 ],

[ 2, 9, 8, 2 ]

]

def minPath(mat):

m,n = len(mat),len(mat[0])

cost = [[0]*n for i in range(m)] # temp storage

for i in range(0,m):

for j in range(0,n):

if i == 0 and j == 0:

cost[i][j] = mat[i][j]

elif i == 0:

cost[i][j] = mat[i][j] + cost[i][j-1]

elif j == 0:

cost[i][j] = mat[i][j] + cost[i-1][j]

if i > 0 and j > 0:

cost[i][j] = mat[i][j] + min(cost[i-1][j],cost[i][j-1]) # no diagonal

#cost[i][j] = mat[i][j] + min(cost[i-1][j-1],cost[i-1][j],cost[i][j-1]) diagonal

return cost[m-1][n-1]

print minPath(mat)

java

public class MinCBoardPath {

public static int find(int[][] A) {

int[][] solution = new int[A.length][A.length]; # temp storage

solution[0][0] = A[0][0];

// fill the first row

for (int i = 1; i < A.length; i++) {

solution[0][i] = A[0][i] + solution[0][i - 1];

}

// fill the first column

for (int i = 1; i < A.length; i++) {

solution[i][0] = A[i][0] + solution[i - 1][0];

}

// path will be either from top or left, choose which ever is minimum

for (int i = 1; i < A.length; i++) {

for (int j = 1; j < A.length; j++) {

solution[i][j] = A[i][j]

+ Math.min(solution[i - 1][j], solution[i][j - 1]);

}

}

return solution[A.length - 1][A.length - 1];

}

public static void main(String[] args) {

int[][] A = {

{ 1, 7, 9, 2 },

{ 8, 6, 3, 2 },

{ 1, 6, 7, 8 },

{ 2, 9, 8, 2 }

};

System.out.println("Minimum Cost Path " + find(A));

}

}

Egg dropping

http://www.geeksforgeeks.org/dynamic-programming-set-11-egg-dropping-puzzle/