algorithm - 关于在 DP 中使用 bool 数组进行内存

Question

我有一个 DP 问题的有效递归解决方案。我想记住它。

目前它取决于两个状态:索引 i和一个 bool 变量 true或 false .

有人可以指出我如何记住它吗？具体来说，我如何初始化内存表 ( dp )？

我很困惑，因为如果我用 false 初始化第二个状态, 我无法区分 false这是由于初始化，而不是实际上是状态值的初始化。

有人可以提供一些建议吗？

谢谢。

进一步澄清:这就是我声明 dp 的方式现在的表:

vector<vector < bool > > dp;

如何初始化内部 vector<bool> ？我不认为我可以将它设置为 true或 false因为我以后无法区分这是执行(解决问题)时生成的值还是初始化值。

编辑:添加代码:

class Solution {
public:
    unordered_map<int, int> m1, m2;
    vector<int> n1, n2;
    vector<vector<int>> v;
    
    int helper(int i, bool parsingNums1) {
        if((parsingNums1 && i>=n1.size()) || (!parsingNums1 && i>=n2.size())) return v[i][parsingNums1]=0;
        if(v[i][parsingNums1]!=-1) return v[i][parsingNums1];
        
        int ans=0;
        
        if(parsingNums1) {
            //we are traversing path 1
            //see if we can switch to path 2
            if(m2.find(n1[i])!=m2.end())
                ans=n1[i] + helper(m2[n1[i]]+1, false);
            ans=max(ans, n1[i] + helper(i+1, true));
        }

        if(!parsingNums1) {
            //we are traversing path 2
            //see if we can switch to path 1
            if(m1.find(n2[i])!=m1.end())
                ans=n2[i] + helper(m1[n2[i]]+1, true);
            ans=max(ans, n2[i] + helper(i+1, false));
        }

        return v[i][parsingNums1]=ans;
    }
    
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        for(int i=0; i<nums1.size(); i++)
            m1[nums1[i]]=i;
        for(int i=0; i<nums2.size(); i++)
            m2[nums2[i]]=i;
        n1=nums1;
        n2=nums2;
        v.resize((nums1.size()>nums2.size()?nums1.size()+1:nums2.size()+1), vector<int>(2,-1));
        
        return max(helper(0, true), helper(0, false))%(int)(1e9+7);
    }
};

我正在解决这个 LeetCode 问题:https://leetcode.com/problems/get-the-maximum-score/

Answer 1

有两种简单的方法可以处理这个问题。

1. 声明另一个vector<vector < bool > > is_stored初始化为 0，当 dp[i][j] 时计算出来，标记is_stored[i][j]作为 1。因此，当您检查特定状态是否被存储时，您可以查看 is_stored。 .

2. 使用 vector< vector < int > >而不是 vector< vector < bool > >并初始化 -1标记为未记住的每个状态。