Algorithm Game - Fishing - Google Interview

Leetcode: Google interview questions #1
有一个游戏，他说是fishing game，给一个数组vector<int> Basket, 比如里面元素
是{2，3，5，1，3，4，7}
有A，B 2个player，规定只能从Basket2端选数字，意思就是A开始的话一开始A只能选2
或者7，然后B选，同样只能2端选。所以比如一开始A选了7，B只能从2和4中选。问给定
数组A能取的最大值。B的策略已知，是greedy，就是总会取最大的那个数。
写一个 int maxA（vector<int>& Basket）；
Lintcode, Coins in a Line III http://www.lintcode.com/en/problem/coins-in-a-line-iii/#
DP, Memoization. iteration待写

int helper(vector<int> &nums, int start, int end, vector<vector<int> > &dp) {

    if (start == end) return 0;

    if (start + 1 == end) {

        return min(nums[start],nums[end]);

    }

  

    if (dp[start][end] != 0) return dp[start][end];

 

    if (nums[start] < nums[end]) {

        end--;

    }else {

        start++;

    }

  

    int play_1 = helper(nums,start + 1,end,dp) + nums[start];

    int play_2 = helper(nums,start,end - 1,dp)  + nums[end];

  

    dp[start][end] = max(play_1,play_2);

    return max(play_1,play_2);

}

 

int play(vector<int> &nums) {

    vector<vector<int> > dp(nums.size(),vector<int>(nums.size(),0));

 

    return max(helper(nums,0,nums.size() - 2, dp) + nums[nums.size() - 1],helper(nums,0,nums.size() - 2, dp) + nums[nums.size() - 1]);

}

Read full article from Leetcode: Google interview questions #1