# Beats 99.55% C++ bottom-up DP solution with explanations

• dp is two-dimensional,
each level i of dp are the numbers with i divisors.
For example, with nums = {1, 2, 3}
dp[2] = {2, 3}
dp[1] = {1}
(dp[0] = {1} for building dp)

``````vector<int> largestDivisibleSubset(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> dp = {{1}};
for (int n : nums) {
for (int i = dp.size() - 1; i >= 0; i--) {
// If a level consist of a divisor of n, push n to the next level
for (int j : dp[i]) {
if (n % j == 0) {
if (dp.size() <= i + 1)
dp.push_back(vector<int>());
dp[i + 1].push_back(n);
break;
}
}
// If n has been pushed to dp, break to next n
if (dp.size() > i + 1 && dp[i + 1].back() == n)
break;
}
}
// Find all the numbers of the subset with the largest one being the first number in the last level
vector<int> result;
int n = dp.back().front();
for (int i = dp.size() - 1; i > 0; i--) {
for (int j : dp[i]) {
if (n % j == 0) {
result.insert(result.begin(), n = j);
break;
}
}
}
return result;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.