Dynamic Programming to Divide and Conquer

Question

I am working on this program converting a divide and conquer algorithm to a dynamic programming algorithm. The algorithm is for sequencing (like DNA) and finding the cost to do so. Just to reiterate the dynamic programming algorithm is working and the divide and conquer one is not and I cannot figure out why.

#include<iostream>
#include <vector>
using namespace std;

int penalty;
int m, n;
char x[] = { 'A', 'A', 'C' }; //, 'A', 'G', 'T', 'T', 'A', 'C', 'C' };
char y[] = { 'T', 'A' }; //,'A' //, 'G', 'G', 'T', 'C', 'A' }; 

//find minimum
int min(int one, int two, int three)
{
    if (one <= two && one <= three)
        return one;
    if (two <= one && two <= three)
        return two;
    return three;
}

//divide and conquer way of find the cost of the optimal path
int optMethod(int i, int j)
{

    if (i == m)
        return  2 * (n - j);
    else if (j == n)
        return 2 * (m - i);
    else {
        if (x[i] == y[j])
            penalty = 0;
        else
            penalty = 1;

        return min(optMethod(i + 1,j + 1) + penalty, optMethod(i + 1,j) + 2, optMethod(i,j + 1) + 2);
    }


}

//dynamic programming way of finding cost of optimal path
void dynamicOptimal(vector<vector<int>>& opt1) {
    for (int i = m; i >= 0; i--) {
        for (int j = n; j >= 0; j--) {
            if (i == m)
                opt1[m][j] = 2 * (n - j);
            else if (j == n)
                opt1[i][n] = 2 * (m - i);
            else {
                if (x[i] == y[j])
                    penalty = 0;
                else
                    penalty = 1;

                opt1[i][j] = min(opt1[i+1][j+1] + penalty, opt1[i+1][j] + 2, opt1[i][j+1] + 2);
            }
        }
    }
}


int main() {
    m = sizeof(x);
    n = sizeof(y);

    //divide and conquer 
    cout << optMethod(0, 0) << endl;

    //dynamic
    vector <vector<int> > optimal(m+1, vector<int>(n+1, 0));
    dynamicOptimal(optimal);
    cout<<optimal[0][0]<<endl;


    cin.get();
    return 0;
}

What I am getting right now is that there is a extra penalty being given but I can't figure out where. [NOTE] I know I did not use the std::min and I know its there

Answer 1

You should change :

if (two <= one && two <= two)
        return two;
    return three;

With :

if (two <= one && two <= three)
        return two;
    return three;