dynamic programming series

1. Longest Common Sequence (LCS)
code from wikipedia:


#!/usr/bin/env python
def lcs(x,y):
    n = len(x)
    m = len(y)
    table = dict()

    for i in range(n):
        for j in range(m):
            if i == 0 or j == 0:
                table[i,j] = 0
            elif x[i-1] == y[j-1]:
                table[i,j] = table[i-1,j-1] + 1
            else:
                table[i,j] = max(table[i-1,j],table[i,j-1])

    def recon(i,j):
        if i == 0 or j == 0:
            return []
        elif x[i-1] == y[j-1]:
            return recon(i-1,j-1) + [x[i-1]]
        elif table[i-1,j] > table[i,j-1]:
            return recon(i-1,j)
        else:
            return recon(i,j-1)

    return recon(n,m)

if __name__ == "__main__":
    x = ['a','b','c','d','e','f','g']
    y = ['b','c','e','f','g']

    print lcs(x,y)

2. edit distance

int editDistance(vector<char> &x, vector<char> &y)
{
int m[x.size()+1][y.size()+1];

/*
m is for bookkeeping distances of x[0...i] y[0...j]
*/
for(int i=0; i<x.size()+1; i++) m[i][0] = 0;
for(int j=0; j<y.size()+1; j++) m[0][j] = 0;
for(int i=1; i<x.size()+1; i++)
{
for(int j=1; j<y.size()+1; j++)
{
int c1 = m[i-1][j-1] + (x[i-1] == y[i-1] ? 0 : 1);
int c23 = min(m[i-1][j] , m[i][j-1]);
m[i][j] = min(c1,c23);
}
}
return m[x.size()][y.size()]
}

3. coin change problem

#include <cstdio>

#include <vector>

#include <algorithm>

using std::sort;

using std::vector;

const int minCoinChange(const int amount, vector<int> &coins)

{

sort(coins.begin(), coins.end());

int f[amount+1][coins.size()];

for(int i=0; i<(amount+1); i++)

{

for(int j=0; j<coins.size(); j++)

{

if(i == 0) {f[i][j] = 0; continue;}

//if(i == coins[j]) {f[i][j] = 1; continue;}

if(j == 0) {f[i][j] = ((i%coins[j] == 0) ? i/coins[j] : 0); continue;}

if(i < coins[j]) {f[i][j] = f[i][j-1]; continue;}

if((f[i-coins[j]][j]+1)<f[i][j-1]) f[i][j] = f[i-coins[j]][j]+1;

else f[i][j] = f[i][j-1];

}

}

for(int i=0; i<(amount+1); i++)

{

for(int j=0; j<coins.size(); j++)

printf("%d ", f[i][j]);

printf("\n");

}

int min = amount;

int cnt = 1;

for(int j=0; j<coins.size(); j++)

{

if(f[amount][j] < min) min = f[amount][j];

}

for(int j=0; j<coins.size(); j++)

{

if(f[amount][j] == min)

{

printf("solution %d: %d = ", cnt++, amount);

int curCoin=j;

int curAmt=amount;

for(int k=0; k < min; k++)

{

if(curAmt >= coins[curCoin] && f[curAmt][curCoin] == f[curAmt - coins[curCoin]][curCoin] + 1)

{

printf("%d ", coins[curCoin]);

curAmt -= coins[curCoin];

}

else

{

curCoin--;

k--;

}

}

printf("\n");

}

}

printf("coins needed for amount %d is %d\n", amount, min);

return min;

}

Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … ,a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3] 

#include <vector>
#include <algorithm>
#include <cstdio>
 
using namespace std;
 
int combinationSum(vector<int> &candidates, int target)
{
        int numCombs;
        int am[candidates.size()+1][target+1];
        for(int i=0; i<=candidates.size(); i++) am[i][0] = 0;
        for(int j=0; j<=target; j++) am[0][j] = 0;
 
        for(int i=1; i<=candidates.size(); i++)
        {
                for(int j=1; j<=target; j++)
                {
                        int cur = candidates[i-1];
                        am[i][j] = am[i-1][j];
                        if(j-cur == 0) am[i][j] = am[i-1][j]+1;
                        if(j-cur > 0)
                        {
                                am[i][j] = am[i-1][j] + am[i][j-cur];                           
                        }
                }
        }
        for(int i=0; i<=candidates.size(); i++)
        {
                for(int j=0; j<=target; j++)
                {
                        printf("%d ", am[i][j]);
                }
                printf("\n");
        }
        return am[candidates.size()][target];
}
 
int main()
{
        int a[] = {2,3,6,7};
        vector<int> candidates(a, a+sizeof(int));
        int allCombs = combinationSum(candidates, 7);
        printf("%d\n", allCombs);
        return 0;
}