如何记忆递归问题以避免重新估计子问题？

Question

我正在尝试解决这个问题： < -given-digit-sequence/

示例： 输入：
输入str =“ 121” 总解码:: 3 :: aba au la

我能够通过递归对此问题进行编码。但是该代码未能处理更大的输入序列（例如，I/P str =111111111111111111111111111111111111111111111111111111111111后成 这是因为我再次计算了子问题。

谁能通过让我知道如何在示例代码下进行记忆来帮助我？

PS-我知道还有其他方法可以解决此问题。但是我不想那样做。 我只想记忆这个解决方案。这将帮助我建立自己的概念。请帮忙。

这是代码：

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

namespace solution3
{
    void solve(string str, string& out, vector<string>& v)
    {
        if (str.size() == 0)
        {
            v.push_back(out);
            return;
        }
        //we have 2 choices:
        //ch#1: take 1st char of str
        //ch#2: take 1st and 2nd chars of str    


        if (str.size() >= 1)//ch#1: take 1st char of str
        {
            string out1 = out;
            string str1 = str;
            int num1 = stoi(str.substr(0, 1)); // converting string at index 0 to integer
            if (num1) // we will not consider if the string at index 0 is zero.
            {
                out1.push_back(('@' + num1)); //<-- It will conevrt 1 into A; 2 into B; and so on.
                str1 = str1.erase(0, 1);//erase the index 0 from str1.
                solve(str1, out1, v);
            }
        }

        if (str.size() >= 2)//ch#2: take 1st and 2nd chars of str
        {
            string out2 = out;
            string str2 = str;
            int num2 = stoi(str.substr(0, 2)); // converting string at index 0 and 1 to integer

            // checking if num2 is a valid number for decoding.
            // num2 should be - NON-ZERO, 1st char is not ZERO, is within the range of 1 and 26. 
            if (num2 && str[0] != '0' && num2 > 0 && num2 <= 26) 
            {
                out2.push_back(('@' + num2));
                //Erase 1st two chars from str
                str2 = str2.erase(0, 1);//erase the index 0 from str1.
                str2 = str2.erase(0, 1);//erase the index 0 from str1.
                solve(str2, out2, v);
            }
        } 
    }
    void alphacode(string str)
    {
        string out;
        vector<string> v; //<-- To store all the Decodings
        solve(str, out, v);

        cout << "Total decoding:: " << v.size() << ":: ";
        for (int i = 0; i < v.size(); i++)
            cout << v[i] << " ";
        cout << endl;
    }
}
int main()
{
    string str = "25114";
    cout << "IpStr:: " << str << endl;
    solution3::alphacode(str);
    cout << "----------------" << endl;
    str = "1111111111";
    cout << "IpStr:: " << str << endl;
    solution3::alphacode(str);
    cout << "----------------" << endl;
    str = "3333333333";
    cout << "IpStr:: " << str << endl;
    solution3::alphacode(str);
    cout << "----------------" << endl;
    str = "202";
    cout << "IpStr:: " << str << endl;
    solution3::alphacode(str);
    cout << "----------------" << endl;
    str = "2010";
    cout << "IpStr:: " << str << endl;
    solution3::alphacode(str);
    cout << "----------------" << endl;
    str = "1111111111111111111111111111111"; //<-- takes too much time! How to solve this?
    cout << "IpStr:: " << str << endl;
    solution3::alphacode(str);
    return 0;
}

Answer 1

您可以记住当前正在使用的每个子字符串，这些子字符串根据情况在删除一个或两个字符后形成。这样的事情：

#include "iostream"
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;


map<string, vector<string>> dp;

namespace solution3
{
    void solve(string str, string& out, vector<string>& v)
    {
        if (str.size() == 0)
        {
            v.push_back(out);
            return;
        }
        //we have 2 choices:
        //ch#1: take 1st char of str
        //ch#2: take 1st and 2nd chars of str   
        if(dp.find(str) != dp.end()) {
            vector<string> current = dp[str];
            for(string s: current) {
                v.push_back(s);
            }
            return;
        } 


        if (str.size() >= 1)//ch#1: take 1st char of str
        {
            string out1 = out;
            string str1 = str;
            int num1 = stoi(str.substr(0, 1)); // converting string at index 0 to integer
            if (num1) // we will not consider if the string at index 0 is zero.
            {
                out1.push_back(('@' + num1)); //<-- It will conevrt 1 into A; 2 into B; and so on.
                str1 = str1.erase(0, 1);//erase the index 0 from str1.
                solve(str1, out1, v);
            }
        }

        if (str.size() >= 2)//ch#2: take 1st and 2nd chars of str
        {
            string out2 = out;
            string str2 = str;
            int num2 = stoi(str.substr(0, 2)); // converting string at index 0 and 1 to integer

            // checking if num2 is a valid number for decoding.
            // num2 should be - NON-ZERO, 1st char is not ZERO, is within the range of 1 and 26. 
            if (num2 && str[0] != '0' && num2 > 0 && num2 <= 26) 
            {
                out2.push_back(('@' + num2));
                //Erase 1st two chars from str
                str2 = str2.erase(0, 1);//erase the index 0 from str1.
                str2 = str2.erase(0, 1);//erase the index 0 from str1.
                solve(str2, out2, v);
            }
        } 
        dp[str] = v;
    }
    void alphacode(string str)
    {
        string out;
        vector<string> v; //<-- To store all the Decodings
        solve(str, out, v);

        cout << "Total decoding:: " << v.size() << ":: ";
        // for (int i = 0; i < v.size(); i++)
        //     cout << v[i] << " ";
        cout << endl;
    }
}
int main()
{
    string str = "25114";
    cout << "IpStr:: " << str << endl;
    solution3::alphacode(str);
    cout << "----------------" << endl;
    str = "1111111111";
    cout << "IpStr:: " << str << endl;
    solution3::alphacode(str);
    cout << "----------------" << endl;
    str = "3333333333";
    cout << "IpStr:: " << str << endl;
    solution3::alphacode(str);
    cout << "----------------" << endl;
    str = "202";
    cout << "IpStr:: " << str << endl;
    solution3::alphacode(str);
    cout << "----------------" << endl;
    str = "2010";
    cout << "IpStr:: " << str << endl;
    solution3::alphacode(str);
    cout << "----------------" << endl;
    str = "1111111111111111111111111111111"; //<-- takes too much time! How to solve this?
    cout << "IpStr:: " << str << endl;
    solution3::alphacode(str);
    return 0;
}