Divide-and-Conquer DP Optimization
(convex/monge/divide_and_conquer_optimization.hpp)

• View this file on GitHub
• Last update: 2026-07-07 18:38:36+09:00
• Include: #include "convex/monge/divide_and_conquer_optimization.hpp"

Overview

Divide-and-conquer DP optimization computes

\[dp[i] = \min_j A(i,j)\]

when the leftmost minimizing index is nondecreasing with i. It evaluates only a narrowed candidate interval for each recursive subproblem.

This header is the DP-facing wrapper around monotone_row_argmin: it returns both optimum values and their candidate indices.

Generic Interface

template <class Value>
auto divide_and_conquer_dp(
    int state_count,
    int candidate_count,
    Value value
);

value(state, candidate) returns one transition value. The return type is DivideAndConquerDpResult<T>:

Member	Meaning
value[i]	Minimum value for state i.
argmin[i]	Leftmost minimizing candidate for state i.

If there are no candidates, every argmin is -1; the corresponding values are placeholders.

Previous-Layer Helper

For the common recurrence

\[dp_{\mathrm{next}}[i] = \min_j \left(dp_{\mathrm{previous}}[j] + cost(j,i)\right),\]

use:

template <class T, class Cost>
auto divide_and_conquer_transition(
    const std::vector<T>& previous,
    int state_count,
    Cost cost
);

Candidates that are invalid for a state can be represented by a sufficiently large value, provided arithmetic does not overflow and the remaining leftmost argmins are still nondecreasing.

Requirement

The leftmost minimizing candidate indices must be nondecreasing over states. The implementation does not verify this condition.

Monge transition matrices satisfy the requirement, but the condition also holds for some matrices that are not Monge.

Complexity

For H states and W candidates, the algorithm uses $O((H+W)\log H)$ transition evaluations and $O(H)$ additional memory.

Example

#include "convex/monge/divide_and_conquer_optimization.hpp"
#include <vector>

int main() {
    std::vector<long long> previous = {0, 4, 7, 9};

    auto result = m1une::convex::divide_and_conquer_transition(
        previous, 6, [](int candidate, int state) {
            long long difference = state - candidate;
            return difference * difference;
        });
}

Depends on

• Monotone Minima (convex/monge/monotone_minima.hpp)

Required by

• Convex All (convex/all.hpp)
• Monge All (convex/monge/all.hpp)

Verified with

• verify/convex/monge/monge_algorithms.test.cpp
• verify/convex/monge/monge_dp_optimization.test.cpp

Code

#ifndef M1UNE_CONVEX_MONGE_DIVIDE_AND_CONQUER_OPTIMIZATION_HPP
#define M1UNE_CONVEX_MONGE_DIVIDE_AND_CONQUER_OPTIMIZATION_HPP 1

#include <type_traits>
#include <utility>
#include <vector>

#include "monotone_minima.hpp"

namespace m1une {
namespace convex {

template <class T>
struct DivideAndConquerDpResult {
    std::vector<T> value;
    std::vector<int> argmin;
};

template <class Value>
auto divide_and_conquer_dp(int state_count, int candidate_count, Value value)
    -> DivideAndConquerDpResult<
        std::decay_t<std::invoke_result_t<Value, int, int>>> {
    using T = std::decay_t<std::invoke_result_t<Value, int, int>>;
    DivideAndConquerDpResult<T> result;
    result.argmin = monotone_row_argmin(state_count, candidate_count, value);
    result.value.resize(state_count);
    for (int state = 0; state < state_count; state++) {
        if (result.argmin[state] != -1) {
            result.value[state] = value(state, result.argmin[state]);
        }
    }
    return result;
}

template <class T, class Cost>
auto divide_and_conquer_transition(const std::vector<T>& previous, int state_count,
                                   Cost cost)
    -> DivideAndConquerDpResult<
        std::decay_t<decltype(std::declval<T>() + cost(0, 0))>> {
    using Result = std::decay_t<decltype(std::declval<T>() + cost(0, 0))>;
    return divide_and_conquer_dp(
        state_count, int(previous.size()),
        [&](int state, int candidate) -> Result {
            return previous[candidate] + cost(candidate, state);
        });
}

}  // namespace convex
}  // namespace m1une

#endif  // M1UNE_CONVEX_MONGE_DIVIDE_AND_CONQUER_OPTIMIZATION_HPP

#line 1 "convex/monge/divide_and_conquer_optimization.hpp"



#include <type_traits>
#include <utility>
#include <vector>

#line 1 "convex/monge/monotone_minima.hpp"



#include <cassert>
#include <functional>
#line 7 "convex/monge/monotone_minima.hpp"

namespace m1une {
namespace convex {

namespace monotone_minima_detail {

template <class Value, class Compare>
void solve(int row_left, int row_right, int column_left, int column_right,
           const Value& value, const Compare& compare, std::vector<int>& answer) {
    if (row_left == row_right) return;
    int row = (row_left + row_right) / 2;
    int best = column_left;
    for (int column = column_left + 1; column < column_right; column++) {
        if (compare(value(row, column), value(row, best))) best = column;
    }
    answer[row] = best;
    solve(row_left, row, column_left, best + 1, value, compare, answer);
    solve(row + 1, row_right, best, column_right, value, compare, answer);
}

}  // namespace monotone_minima_detail

template <class Value, class Compare = std::less<>>
std::vector<int> monotone_row_optima(int row_count, int column_count, Value value,
                                     Compare compare = Compare()) {
    assert(row_count >= 0);
    assert(column_count >= 0);
    std::vector<int> answer(row_count, -1);
    if (row_count == 0 || column_count == 0) return answer;
    monotone_minima_detail::solve(0, row_count, 0, column_count, value, compare, answer);
    return answer;
}

template <class Value>
std::vector<int> monotone_row_argmin(int row_count, int column_count, Value value) {
    return monotone_row_optima(row_count, column_count, value, std::less<>());
}

template <class Value>
std::vector<int> monotone_row_argmax(int row_count, int column_count, Value value) {
    return monotone_row_optima(row_count, column_count, value, std::greater<>());
}

template <class T>
std::vector<int> monotone_row_argmin(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return monotone_row_argmin(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

template <class T>
std::vector<int> monotone_row_argmax(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return monotone_row_argmax(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

}  // namespace convex
}  // namespace m1une


#line 9 "convex/monge/divide_and_conquer_optimization.hpp"

namespace m1une {
namespace convex {

template <class T>
struct DivideAndConquerDpResult {
    std::vector<T> value;
    std::vector<int> argmin;
};

template <class Value>
auto divide_and_conquer_dp(int state_count, int candidate_count, Value value)
    -> DivideAndConquerDpResult<
        std::decay_t<std::invoke_result_t<Value, int, int>>> {
    using T = std::decay_t<std::invoke_result_t<Value, int, int>>;
    DivideAndConquerDpResult<T> result;
    result.argmin = monotone_row_argmin(state_count, candidate_count, value);
    result.value.resize(state_count);
    for (int state = 0; state < state_count; state++) {
        if (result.argmin[state] != -1) {
            result.value[state] = value(state, result.argmin[state]);
        }
    }
    return result;
}

template <class T, class Cost>
auto divide_and_conquer_transition(const std::vector<T>& previous, int state_count,
                                   Cost cost)
    -> DivideAndConquerDpResult<
        std::decay_t<decltype(std::declval<T>() + cost(0, 0))>> {
    using Result = std::decay_t<decltype(std::declval<T>() + cost(0, 0))>;
    return divide_and_conquer_dp(
        state_count, int(previous.size()),
        [&](int state, int candidate) -> Result {
            return previous[candidate] + cost(candidate, state);
        });
}

}  // namespace convex
}  // namespace m1une

Back to top page