Почему рекурсия + запоминание дает TLE?

Хорошо, мы знаем, что временные сложности итератива и запоминания одинаковы. но все равно на литкоде за это дается TLE. Проблема: https://leetcode.com/problems/partition-equal-subset-sum/ Также я использую Call by Reference, но все же. Я делаю это неправильно или что-то упустил?

Код :

public:
    bool isPresent(vector<int>& a, const double& sum, int i, vector<vector<bool>> &dp) {
        int n = a.size();
        if (i == n) return false;
        
        if (sum < 0) return false;
        if (sum == 0) return true;
        
        if (dp[i][sum] == true) return true;
        
        if (isPresent(a, sum - a[i], i+1, dp) || isPresent(a, sum, i+1, dp))
            return dp[i][sum] = true;
        return dp[i][sum] = false;
    }
    bool canPartition(vector<int>& a) {
        
        int n = a.size();
        int s=0;
        for(int i=0;i<n;i++) {
            s += a[i];
        }
        double sum = ((double)s) / 2.0;
        vector<vector<bool>> dp(n+1, vector<bool> (sum+1, false));
        
        return isPresent(a, sum, 0, dp);
    }
};

c++

25.12.2020 11:26

Стоит ли изучать PHP в 2023-2024 годах?

Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...

Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией

В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.

Приемы CSS-макетирования - floats и Flexbox

Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...

Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest

В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...

Концепция локализации и ее применение в приложениях React ⚡️

Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...

Пользовательский скаляр GraphQL

Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...

Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы используете свою заметку только тогда, когда dp[i][sum] == true. Другими словами, вы не используете запомненную информацию о том, что для этого параметра не будет никакого решения.

Вам понадобится (как минимум) таблица заметок с 3 состояниями: «истина», «ложь» и «еще не рассчитано».

Вот один пример с использованием другой таблицы dpValid:

public:
    bool isPresent(vector<int>& a, const double& sum, int i, vector<vector<bool>> &dp, vector<vector<bool>> &dpValid) {
        int n = a.size();
        if (i == n) return false;
        
        if (sum < 0) return false;
        if (sum == 0) return true;
        
        if (dpValid[i][sum] == true) return dp[i][sum];
        
        dpValid[i][sum] = true; // [i][sum] won't be visited in further recursion, so we can raise flag at here
        if (isPresent(a, sum - a[i], i+1, dp, dpValid) || isPresent(a, sum, i+1, dpValid))
            return dp[i][sum] = true;
        return dp[i][sum] = false;
    }
    bool canPartition(vector<int>& a) {
        
        int n = a.size();
        int s=0;
        for(int i=0;i<n;i++) {
            s += a[i];
        }
        double sum = ((double)s) / 2.0;
        vector<vector<bool>> dp(n+1, vector<bool> (sum+1, false));
        vector<vector<bool>> dpValid(n+1, vector<bool> (sum+1, false));
        
        return isPresent(a, sum, 0, dp, dpValid);
    }
};

Работал!!! но все же итеративные быстрее, лол. Спасибо.

— 25.12.2020 11:38

25.12.2020 11:32