zippon.wu
BAN USERAdd DP to it by using map (or you can use 2-D array too)
map<pair<int, int>, int, PairCmp> DP_map;
typedef pair<int, int> Key;
// Before that, you need to implement a comparison operator for pair<int, int>, say
struct PairCmp {
bool operator() (const Key& p1, const Key& p2) const {
if (p1.first < p2.first)
return true;
else if (p1.first = p2.first)
return p1.second < p2.second;
else
return false;
}
int max_coin( int *coin, int start, int end ):
if start > end:
return 0
if (DP_map.find(Key(start, end)) != DP_map.end())
return DP_map[Key(start, end)];
int a = coin[start] + min( max_coin( coin, start+2,end ), max_coin( coin, start+1,end-1 ) )
int b = coin[end] + min( max_coin( coin, start+1,end-1 ), max_coin( coin, start,end-2 ) )
int ret = max(a, b);
DP_map[Key(start, end)] = ret;
return ret;
}
(pseudo-code only )
Say, the index value (started from 0) corresponds to (is one bit of) the original number Num.
We try to get the number of digits (n) for Num.
Then for the total number of digits until Num, we have the following equation:
And what we need is:
we can solve the above equation to get Num.
Then, we need to refine and get the specific digital value we want.
- zippon.wu March 06, 2013we first convert Num to a string and select the right one we want.