我想使用记忆优化我的递归解决方案来解决不同的子序列问题

Question

问题陈述是：给定两个序列 A 和 B，计算序列 A 中唯一的路数，以形成与序列 B 相同的子序列。子序列：字符串的子序列是在不打乱剩余字符的相对位置的情况下，通过删除一些（可以是none）字符从原始字符串形成的新字符串。（即，“ACE”是“ABCDE”的子序列，而“AEC”不是）。

目标：我想使用 dp

优化我的递归解决方案

我的方法：我正在尝试制作给定字符串的每个可能的子序列，如果子序列与模式 ans 匹配，则为 ans=ans+1.

我想记住解决方案并使用 dp 来优化时间复杂度，但不知道该怎么做。

代码：

int funct(string &given,string &target,string &curr, int index)
{
    if(curr == target)
    {
        return 1;
    }
    if( index >= given.size() )
    return 0;
    int without = funct(given,target,curr,index+1);
    curr.push_back(given[index]);
    int with = funct(given,target,curr,index+1);
    curr.pop_back();
    return with+without;
}
int Solution::numDistinct(string A, string B) 
{
    string s;
    return funct(A,B,s,0);
}

Answer 1

设A的长度为L1，B的长度为L2。
设 f(i,j) 是一个函数，它给出了从序列 A(i...L1-1) 中获取序列 B(j...L2-1) 的方法数，那么你问题的答案就是 f(0,0).
请注意序列A(i...L1-1)表示子串A(i...L1-1)，B(j...L2-1)表示子串B( j...L2-1).

这里是用C++写的代码：

int memo[100][100];
string A, B;

int f(int i, int j) {
    if (i >= A.length() || j >= B.length()) return 0;
    if (A[i] == B[j]) {
        if (j == B.length() - 1)
            memo[i][j] = 1 + f(i + 1 , j);
        else
            memo[i][j] = f(i + 1, j + 1) + f(i + 1, j);
    }
    else {
        memo[i][j] = f(i + 1, j);
    }
    return memo[i][j];
}

我想使用记忆优化我的递归解决方案来解决不同的子序列问题

I want to use optimise my recursive solution using memoisation for Distinct Subsequences problem

recursion

dynamic-programming