dynamic programming

the max coin problem

#include<iostream>
#include<vector>

using namespace std;
int max_coin(vector<int> pots)
{
vector<vector<int>> dp_table;
int pot_num=pots.size();
dp_table.resize(pot_num);
for(int i=0;i<pot_num;i++)
{
dp_table[i].resize(pot_num);
for(int j=0;j<i;j++)
dp_table[i][j]=0;
}
for(int k=0;k<pot_num;k++)
{
for(int i=0;i<pot_num;i++)
{
int j=i+k;
if(j>=pot_num)
continue;
double pots1,pots2;
if(i+2<pots.size() && j-1>=0)
pots1=pots[i]+min(dp_table[i+2][j],dp_table[i+1][j-1]);
else
pots1=pots[i];
if(i+1<pots.size() && j-2>=0)
pots2=pots[j]+min(dp_table[i+1][j-1],dp_table[i][j-2]);
else
pots2=pots[j];
dp_table[i][j]=max(pots1,pots2);
}
}
return dp_table[0][pot_num-1];
}