math/partition-table.hpp

• View this file on GitHub
• Last update: 2023-07-08 14:12:19+09:00
• Include: #include "math/partition-table.hpp"

Depends on

• math/base.hpp

Code

#pragma once

#include "./base.hpp"

#include <vector>

namespace matumoto {
  template <typename T>
  vector<vector<T>> PartitionTable(int n, int k) {
    vector<vector<T>> dp(n + 1, vector<T>(k + 1));
    dp[0][0] = 1;
    for (int i = 0; i <= n; i++) {
      for (int j = 1; j <= k; j++) {
        if (i - j >= 0)
          dp[i][j] = dp[i][j - 1] + dp[i - j][j];
        else
          dp[i][j] = dp[i][j - 1];
      }
    }
    return dp;
  }
} // namespace matumoto

#line 2 "math/partition-table.hpp"

#line 2 "math/base.hpp"

namespace matumoto {
  using namespace std;
  using ll = long long;
} // namespace matumoto
#line 4 "math/partition-table.hpp"

#include <vector>

namespace matumoto {
  template <typename T>
  vector<vector<T>> PartitionTable(int n, int k) {
    vector<vector<T>> dp(n + 1, vector<T>(k + 1));
    dp[0][0] = 1;
    for (int i = 0; i <= n; i++) {
      for (int j = 1; j <= k; j++) {
        if (i - j >= 0)
          dp[i][j] = dp[i][j - 1] + dp[i - j][j];
        else
          dp[i][j] = dp[i][j - 1];
      }
    }
    return dp;
  }
} // namespace matumoto

Back to top page