Об использовании логического массива для мемоизации в DP - PullRequest
Новая
       128

Об использовании логического массива для мемоизации в DP

3 голосов
/ 07 августа 2020

У меня есть рабочее рекурсивное решение проблемы DP. Я хочу sh, чтобы запоминать его.

В настоящее время это зависит от двух состояний: индекса i и логической переменной true или false.

Кто-нибудь может указать как я мог это запомнить? В частности, как я могу инициализировать таблицу мемоизации (dp)?

Я запутался, потому что, если я инициализирую второе состояние с помощью false, я не смогу различать false, которые происходит из-за инициализации, а не из-за того, где на самом деле это значение состояния.

Может кто-нибудь дать совет?

Спасибо.

Для дальнейшего пояснения: Это вот как я прямо сейчас объявляю таблицу dp:

вектор > dp;

Как инициализировать внутренний vector<bool>? Я не думаю, что могу установить его либо на true, либо на false, так как позже я не смогу различить guish, если это значение , сгенерированное при выполнении (решение проблема) или значение инициализации.

Изменить: Добавление кода: 

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/

1 Ответ

3 голосов
/ 07 августа 2020

Есть два простых способа справиться с этим.

  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 для каждого состояния отметить как не запомненное.

...