What’s wrong with this solution. I have used 2D dp table to solve it, with one state as number of tables used and another state represents index of the guest to be placed.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define IOS ios::sync_with_stdio(0); cin.tie(0);
const int inf = 1e10;
signed main() {
IOS;
int t; cin >> t;
while(t--) {
int n, k; cin >> n >> k;
vector<int> a(n);
int num_families = 0;
for(auto &num : a) {
cin >> num;
num_families = max(num_families, num);
num -= 1;
}
vector<vector<int>> count(num_families, vector<int>(n, 0));
for(int i=0;i<num_families;i++) {
for(int j=0;j<n;j++) {
if(j == 0) {
count[i][j] = (i == a[j]);
} else {
count[i][j] = count[i][j-1] + (i == a[j]);
}
}
}
// for(int i=0;i<num_families;i++) {
// cout << "FAMILY " << i + 1 << " : ";
// for(auto num : count[i]) {
// cout << num << " ";
// }
// cout << "\n";
// }
vector<vector<int>> dp(n + 1, vector<int>(n + 1, inf));
/**
* @brief
* dp[i][j] - denotes the minimum cost associated to place first 'i' guests at 'j' tables.
* At every index 'i' we have two choices
* 1. Place the 'i'th guest with 'i-1'th guest
* 2. Place the 'i'th guest on a new table
*/
dp[1][1] = k;
dp[1][0] = inf;
dp[0][1] = k;
for(int i=2;i<=n;i++) {
dp[i][1] = dp[i-1][1];
int count_of_quarell = count[a[i-1]][i-1];
int to_add = 0;
if(count_of_quarell == 2) {
to_add = 2;
} else if(count_of_quarell > 2) {
to_add = 1;
}
dp[i][1] += to_add;
}
for(int j=2;j<=n;j++) {
dp[1][j] = dp[1][j-1] + k;
}
for(int i=2;i<=n;i++) {
for(int j=2;j<=n;j++) {
// 1. cost associated with adding 'i'th guest to 'j'th table = count of index 'k' such that 0 <= k <= i-1 and a[k] == a[i] => count[a[i]][i]
// 2. cost associated with placing 'i'th guest on a new table => k
// STARTING A NEW TABLE AND PLACING GUEST 'i' AT THIS NEW TABLE
dp[i][j] = min(dp[i][j], dp[i-1][j-1] + k);
int count_of_quarell = count[a[i-1]][i-1];
int to_add = 0;
if(count_of_quarell == 2) {
to_add = 2;
} else if(count_of_quarell > 2) {
to_add = 1;
}
// PLACING THE 'i'th GUEST WITH 'i-1'th GUEST
dp[i][j] = min(dp[i][j], dp[i-1][j] + to_add);
}
}
int ans = inf;
for(int j=1;j<=n;j++) {
// cout << dp[n][j] << " ";
ans = min(ans, dp[n][j]);
}
// cout << "\n";
cout << ans << "\n";
}
}