DP

套路:最长 , 最优,最大,最小,最长,计数

先写出递归式

string sa = "abcd";
string sb = "becd";

int f(int a, int b)
{
    if (a == 0 || b == 0)return 0;
    //最小规模为2个字符的比较
    if (sa[a] == sb[b])
    {
        return  1+ f(a-1,b-1) ;//如果该2字符相等,那么计算下一条,最大程度加1
    }
    else
    {
        return max( f(a - 1, b), f(a, b - 1));// 如果不等 那么 a下一条或b下一条选择最大
    }

}

转换为DP的递推式,

    int arr[10][10];
    memset(arr, 0, 4 * 10 * 10);


    for (int a = 1; a <= 4; a++)
    for (int b = 1; b <= 4; b++)
    {
        if (sa[a] == sb[b])
        {
            arr[a][b] = 1 + arr[a - 1][b - 1];
        }
        else
        {
            arr[a][b] = max(arr[a + 1][b], arr[a][b + 1]);
        }




    }

    cout << arr[4][4]<<endl;

评论

暂无评论