In this tutorial, I will give you examples of using dynamic programming for solving the following problems:
1)Minimum number of coins for summing X.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
int c[]={1,3,4}; // value of coins int k=3; //number of cpins that we have /* The d[20] array is for memorization, for instance if we computed f_coin_problem_memo(3), we put this value in d[3] and we don't compute it again, we just use d[3] instead of f_coin_problem_memo(3) */ int d[20]; int f_coin_problem_memo(int x) { if (x < 0) return 1e9; if (x == 0) return 0; if (d[x]) return d[x]; int u = 1e9; int u_old = 1e9; for (int i = 0; i < k; i++) { u_old=u; u = std::min(u, f_coin_problem_memo(x-c[i]) +1); } d[x] = u; return d[x]; } |
|
1 2 |
The minimum number of coins from the set {1,3,4} to sum up value of 12 is: 3 |
2)The most (least) costly path on a grid (dynamic time warping).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
finding a path in an n × n grid from the upper-left corner to the lower-right corner. We are only allowed to move right or down. 1,1 1,2 .... 1,X 2,1 2,2 .... 2,X . . . Y,1 Y,2 .... Y,X 3 7 9 2 7 9 8 3 5 5 1 7 9 8 5 3 8 6 4 10 6 3 9 7 8 */ int grid[5][5]={{3,7, 9, 2, 7},{9, 8, 3 ,5 ,5},{1, 7 ,9 ,8 ,5},{3, 8, 6 ,4 ,10},{6, 3 ,9 ,7 ,8}}; int memo[5][5]{{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1}}; std::vector<int>x_solution,y_solution; int f_paths_in_grid(int y,int x) { if((x==0)&& (y==0)) { memo[y][x]=grid[0][0]; } else if (x==0) { if(memo[y][x]<0) { memo[y][x] =f_paths_in_grid(y-1,x) +grid[y][x]; } } else if(y==0) { if(memo[y][x]<0) { memo[y][x]=f_paths_in_grid(y,x-1) +grid[y][x]; } } else if(memo[y][x]<0) { memo[y][x]=std::max(f_paths_in_grid(y,x-1) ,f_paths_in_grid(y-1,x) )+grid[y][x]; } return memo[y][x]; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
maximum sum on a path from the upper-left corner to the lower-right corner is: 67 3|10|19|21|28| --------------- 12|20|23|28|33| --------------- 13|27|36|44|49| --------------- 16|35|42|48|59| --------------- 22|38|51|58|67| --------------- |
3)Levenshtein edit distance.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
int LevenshteinDistance(std::string s, std::string t ) { int cost; /* base case: empty strings */ if (s.length() == 0) return t.length(); if (t.length() == 0) return s.length(); /* test if last characters of the strings match */ if (s.at(s.length()-1) == t.at(t.length()-1) ) cost = 0; else cost = 1; /* return minimum of delete char from s, delete char from t, and delete char from both */ return std::min( std::min(LevenshteinDistance(s.substr(0, s.size()-1 ),t ) + 1,LevenshteinDistance(s , t.substr(0, t.size()-1 )) + 1 ) , LevenshteinDistance(s.substr(0, s.size()-1 ), t.substr(0, t.size()-1 )) + cost ); } |
|
1 2 |
The Levenshtein distance between saturday and sunday is: 3 |
4)Seam Carving. I have written a tutorial on that here and the recursive part is in the following lines:
|
1 2 3 4 5 |
for x=2:rows for y=1:cols M(x+1,y+1)=score_matrix(x,y)+ min( [M(x-1+1,y-1 +1) , M(x-1+1,y+1), M(x-1+1,y+1+1) ] ); end end |
The examples are taken from “Competitive Programmer’s Handbook” written by Antti Laaksonen.
