Динамическое программирование для разделения и покорения

Question

Я работаю над этой программой, превращая алгоритм разделения и покорения в динамический алгоритм программирования. Алгоритм предназначен для секвенирования (например, ДНК) и определения стоимости для этого. Просто повторить динамический алгоритм программирования работает, а разделение и победить - нет, и я не могу понять, почему.

#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; 
} 

То, что я получаю прямо сейчас, это то, что дается дополнительное наказание, но я не могу понять, где. [Примечание] Я знаю, что я не использовал зЬй :: мин, и я знаю его там

Answer 1

Вы должны изменить:

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

С:

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