Maximum Coins Value

这个题来自于《算法设计与分析基础第3版》8.1例1. 是一个很典型的动归问题。
给定n个硬币，从中选出任意多个，但是不能连续选择两个相邻的硬币，例如选了第i个，那么就不能再选第i+1个了。问怎么取才能得到的硬币的value最大。

Discussion

上述的最大金额用F[n]表示，我们可以选择包括最后一个硬币和不包括最后一个硬币，两种情况的最大值就是F[n]了。
很容易写出递推公式F[n] = max{F[n-2]+coins[n-1], F[n-1]}, n>2
初始情况F[0] = 0, F[1] = coins[0]

写出来递推公式以后就完全不难了，跟Fibonacci的公式很像了，算法上是一模一样的。

Solution

//O(n) run time
//O(n) space
 int maxCoinValues(vector<int> &coins) {
     int n = coins.size();
     if (n == 0) return 0;
     vector<int> f(n + 1, 0);
     f[1] = coins[0];
     int a = 0;
     int b = coins[0];
     for (int i = 2; i <= n; i++) {
         f[i] = max(f[i - 1], f[i - 2] + coins[i - 1]);
     }
     return result;
 }

improve to save space

//O(n) run time
//O(1) space
 int maxCoinValues(vector<int> &coins) {
     int n = coins.size();
     if (n == 0) return 0;
     f[1] = coins[0];
     int a = 0;
     int b = coins[0];
     int result = b;
     for (int i = 2; i <= n; i++) {
         result = max(b, a + coins[i - 1]);
         a = b;
         b = result;
     }
     return result;
 }

Follow up

如果是要求那些coins组成了当前的最大值呢？增加一个回溯的过程，看哪些硬币被选出来了。

  vector<int> maxCoinValues2(vector<int> &coins) {
     int n = coins.size();
     vector<int> f(n + 1, 0);
     f[1] = coins[0];
     vector<int> result;
     for (int i = 2; i <= n; i++) {
         f[i] = max(f[i - 1], f[i - 2] + coins[i - 1]);    
     }
     //backtracking to find out which coin is selected
     int i = n;
     while (i >= 2) {
         //f[i] = max(f[i-1], f[i-2]+a[i-1];
         if (f[i - 2] + coins[i - 1] > f[i - 1]) {
             result.emplace_back(i - 1);
             i = i - 2;
         }
         else {
             if (i == 2) {
                 result.emplace_back(0); //coins[1] is not included, so coins[0] must be one part of result;
             }
             i--;
         }
     }
     return result;
 }