关于在 DP 中使用布尔数组进行记忆

Question

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

目前它取决于两个状态：索引i和布尔变量true或false.

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

我很困惑，因为如果我用 false 初始化第二个状态，我将无法区分由于初始化而导致的 false 和它实际所在的状态状态值。

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

谢谢。

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

vector<vector < bool > > dp;

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

编辑：添加代码：

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

有 2 种简单的方法可以处理此问题。

声明另一个初始化为0的vector<vector < bool > > is_stored，当计算dp[i][j]时，将is_stored[i][j]标记为1。所以当你检查特定状态时正在背诵中，可以查看is_stored.
使用vector< vector < int > >代替vector< vector < bool > >并初始化-1到每个状态以标记为未记忆。

Answer 2

另一种存储值的方法是使用 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);

// 至 store/memoize 值
boolean result = someDPmethod(); map.put(key, result);

Answer 3

在 C# 中，您可以使用 nullable value types。

A nullable value type T? represents all values of its underlying value type T and an additional null value. For example, you can assign any of the following three values to a bool? variable: true, false, or null. An underlying value type T cannot be a nullable value type itself.

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

您可以通过将 dp 备忘录初始化为

在 C++ 中模拟此操作

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

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

关于在 DP 中使用布尔数组进行记忆

About using a boolean array for memoization in a DP

algorithm

memoization

dynamic-programming