Ronzii's Blog

Just your average geek's blog

Project Euler Problem 18,67

#include <iostream>
using namespace std;
int main ()
{
    int row;
    int array [102] [102];
    cin >> row;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j <= i; j++)
            cin >> array [i] [j];
    }
    for( int i = row - 2; i >= 0; i--)
    {
        for(int j = 0; j <= i; j++ )
        {
            array[i][j]+=max( array[i + 1][j],array[i + 1][j + 1]);
        }
    }
    cout<<array[0][0];
    return 0;
}

March 26, 2012 Posted by | C++, Dynamic Programming | , , , , | Leave a comment

Counting Change Problem II

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int coinChange(vector<int> v,int N)
{
    int *s = new int[N+1];
    int n = v.size();
    s[0] = 1;
    for(int i=1; i<=N; i++) s[i] = 0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j+v[i]<=N; j++)
        {
            s[j+v[i]]+=s[j];
        }
    }
    return s[N];
}
int main()

{
    int value[] = {1,5,10};
    int n = sizeof(value)/sizeof(value[0]);
    vector<int> v(value,value+n);
    int N;
    while(cin>>N && N)
        cout<<coinChange(v,N)<<endl;
    return 0;
}

March 19, 2012 Posted by | C++, Dynamic Programming | , , , , | Leave a comment

Longest Common Substring

#include <iostream>
#include <cstring>
using namespace std;
int LongestCommonSubString(string first,string second)
{
    int n1 = first.length(), n2 = second.length(),max=0;
    if(n1==0||n2==0) return 0;
    if(n1<n2) swap(first,second);
    int *current = new int[n2];
    int *previous = new int[n2];
    for(int i=0; i<n1; i++)
    {
        for(int j=0; j<n2; j++)
        {
            if(first[i]!=second[j])
                current[j] = 0;
            else if(i==0||j==0)
                current[j] = 1;
            else
                current[j] = previous[j-1] + 1;

            if(max<current[j])
                max = current[j];
        }
        swap(previous,current);
    }
    delete [] previous;
    delete [] current;
    return max;
}
int main()
{
    cout<<LongestCommonSubString("handler","sandollar");
    return 0;
}

February 27, 2012 Posted by | C++, Dynamic Programming | , , , , , , , | Leave a comment