分而治之的动态规划

Question

我正在研究这个程序，将分而治之算法转换为动态规划算法。该算法用于测序（如 DNA）并找出这样做的成本。只是重申动态规划算法有效，分而治之算法无效，我不明白为什么。

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

我现在得到的是额外的惩罚，但我不知道在哪里。 [注意] 我知道我没有使用 std::min 我知道它在那里

Answer 1

你应该改变：

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

有：

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

分而治之的动态规划

Dynamic Programming to Divide and Conquer

c++

algorithm

dynamic-programming

divide-and-conquer