在动态规划中，如何使用布尔型数组进行记忆化？

Question

我有一个递归解决动态规划问题的有效解法。我想将其存入记忆化。

目前它依赖于两个状态：索引i和布尔变量true或false。

请问有人能指出我如何进行记忆化吗？具体来说，我该如何初始化记忆化表(dp)？

我很困惑，因为如果我用false来初始化第二个状态，我就无法区分初始化产生的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/

- user8305079

---

@YashShah，我该如何进行记忆化？例如，如果它是vector<vector < int > > dp;，我可以使用“-1”初始化内部的vector<int>，这样我就可以通过检查dp[0][1] != -1来直接返回。 - user8305079

可以使用0表示false，1表示true，-1表示null，而不是使用bool。 - Yash Shah

是的... 就像这样 vector<int> dp = {-1}; 我是正确的吗？ - Yash Shah

现在，我正在使用一个 bool；所以如果我理解你的意思正确的话，我认为你建议我使用一个 int。因此，基本上是 vector<vector<int>> 并用 -1 初始化内部的 vector<int>。这不就是你建议的吗？ - user8305079

是的...你懂的。 - Yash Shah

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，标记未记忆化。

- potter1024

Answer 2

在C#中，您可以使用可空值类型。

可空值类型T？表示其基础值类型T的所有值以及额外的null值。例如，您可以将以下三个值之一分配给bool？变量：true、false或null。基础值类型T本身不能是可空值类型。

您可以使用null来指示未访问或未处理的dp状态。

您可以通过将dp备忘录初始化为来模拟此过程。

vector<vector<bool*>> dp( m, vector<bool*>(n, nullptr) );

现在您可以使用nullptr作为未处理的dp状态的指示符。

- Ahmed Elghrbawy

Answer 3

另一种存储值的方法是使用 Map<String, Boolean> map = new HashMap<String, Boolean>(); // just a java version，然后您可以通过追加 i 和 j 来创建键，并将相应的布尔值存储到该键中。例如： String key = i + ',' + j;。// 为了验证我们之前是否计算过数据：if(map.containsKeys(key)) return map.get(key);。// 要存储/记忆化值: boolean result = someDPmethod(); map.put(key, result);。

- parag mangal

---

或者我们可以使用Boolean[]（对象）数组进行记忆化，而不是boolean[]（原始）数组。然后默认情况下该值将为null，一旦获取该值，我们就可以存储true或false的值。 例如： `Boolean [] mem = new Boolean [5];mem [0] = false;//这里mem [0]将为false，mem [1]将为null` - mohamed haleem

Answer 4

在Java中，我发现克服这个问题的最佳方法之一是使用布尔类2D数组。由于Boolean[][] dp= new Boolean[n][m]被初始化为null，因此不存在与预初始化false值和更新false值相关的歧义。

因此，可以这样做：

if(dp[i][j]!=null) return dp[i][j]

希望这个回答解决了你的问题。

- sam2611