Has anybody solved this using DP?

# DP Solution needed!

**meghashyamc**#2

Yes, I did but the DP solution (at least top down) is not being accepted due to stack size.

Classic unbounded knapsack plus back pointer to generate the indexes.

```
vector<int> bday(int R, vector<int>& p) {
int n = (int)p.size();
vector<int> dp(R + 1, -1);
vector<int> back(R + 1);
back[0] = 0;
for (int r = 0; r <= R; r++) {
for (int i = 0; i < n; i++) {
if (r >= p[i] && dp[r] < dp[r - p[i]] + 1) {
dp[r] = dp[r - p[i]] + 1;
back[r] = i;
}
}
}
vector<int> ans;
int r = R;
while (r >= 0 && (r - p[back[r]]) >= 0) {
ans.push_back(back[r]);
r = r - p[back[r]];
}
return ans;
}
```

The lexicographic constraint is solved by using dp[r] < dp[r - p[i]] + 1 (i.e. use < instead of <=), then for a specific resistance you save the index of the kick power that gives you the maximum number of kicks for that resistance (thus, by going backward you generate the steps back). Furthermore, since the kicks have to be smaller than the resistance we have to do this while (r >= 0 && (r - p[back[r]]) >= 0) when you generate the answer.

This was my solution.

The way of thinking: the subproblem is the maximum number of kicks for the resistance r, then for the resistance r+1 you maximize the number of kicks (without exceeding R) by trying all the kicks (choosing the one that maximizes the number - lexicographically: donâ€™t choose one that gives the same number).

https://paste.ofcode.org/vWHbauSQ9bVyY25yMzMFWY

the only problem i faced in creating a dp array was it was giving memory limit. but it worked when i used heap memory

i dont see why you got an AC

you are considering that your answer WILL HAVE TO BE r which is not importantâ€¦

it might happen that R-2/R-3 had more kicks or lower lexicographic permutation

infact i dont understand how its ever possible to ensure a lower permuataion of indices without actually comparing the answersâ€¦

i too solved using unbounded knapsackâ€¦got my code acceptedâ€¦try uncommenting the commented part and you will understand what i am doing

```
int dp[15000500];
int parent[15000500];
vector<int> Solution::solve(int B, vector<int> &A) {
int n = A.size();
memset(dp,-1,sizeof(dp));
for(int i=0;i<=B;i++)
parent[i] = n+5;
dp[0] = 0;
for(int i=0;i<=B;i++)
{
for(int j=0;j<n;j++)
{
if(A[j]<=i && dp[i-A[j]]!=-1)
{
if( (dp[i-A[j]]+1>dp[i]) || (dp[i-A[j]]+1==dp[i] && parent[i]>j) )
{
parent[i] = j;
dp[i] = dp[i-A[j]]+1;
}
}
}
}
vector<int>retval;
int remember = -1;
for(int i=B;i>-1;i--)
{
int ans = i;
vector<int>temp;
if(dp[ans]!=-1 && dp[ans]>=dp[remember])
{
while(ans!=0)
{
temp.push_back(parent[ans]);
ans -= A[parent[ans]];
}
}
// cout<<i<<": ";
// for(auto it:temp)
// cout<<it<<" ";
// cout<<endl;
if(temp.size()>retval.size())
{
remember = i;
retval = temp;
}
else if(temp.size()==retval.size())
{
bool flag = false;
for(int j=0;j<temp.size();j++)
{
if(retval[j]>temp[j])
{
flag = true;
break;
}
else if(retval[j]<temp[j])
{
break;
}
}
if(flag)
{
remember = i;
retval = temp;
}
}
}
return retval;
}
```

**geetam-sgdz**#8

Excellent soln and thinking !! I was doing it by 2d dp therefore thinking about lexecographic constraint became though for me . Take a bow