# Algorithm - Medium
###### tags: `HackerRank`

## The Coin Change Problem (DP)
- 題目

- 想法
:::info
- 假設使用m種幣值組合成n元的方法數可表示成 $f(m, n)$
則 $f(m, n) = f(m-1, n) + f(m, n-C_m)$
其中$C_i$代表第$i$種幣值

- 依序求出各種$f(i, j)$的值並記錄，就可以算出目標

Note: 使用遞迴會造成大量Overhead，時間複雜度($O(f(n))$)會大幅增加，因此應該避免使用`

//遞迴版本
long getWays(int n, int c_count, long* c) {
    if (n == 0) 
        return 1;
    
    if (n < 0)
        return 0;
        
    if (c_count <= 0 && n > 0)
        return 0;
        
    return getWays(n, c_count -1, c) + getWays(n - c[c_count - 1], c_count, c);
}

:::

//DP版本
long storage[51][251];

long getWays(int n, int m, long* c) {
    for (int i = 0; i < m+1; i++) {
        storage[i][0] = 1; 
        //printf("%d ", storage[i][0]);
    }
    
    for (int j = 1; j < n+1; j++) {
        storage[0][j] = 0;
        //printf("%d ", storage[0][j]);
        
    }
    
    for (int k = 1; k < m+1; k++) {
        for (int l = 1; l < n + 1; l++) {  
            long y = (l-c[k-1] >= 0) ? storage[k][l-c[k-1]]:0;
            storage[k][l] = storage[k-1][l] + y;
            //printf("storge[%d][%d] = %d ", k, l, storage[k][l]);
        }
        
    }
/*
    for (int i = 0; i < m+1; i++) {
        for (int j = 0; j < n+1; j++)
            printf("%d ", storage[i][j]);
    }
*/
    return storage[m][n];
}

- 分析
- 時間複雜度 $O(mn)$
- 空間複雜度 $O(mn)$

## Equal
- 題目
:::success
若有n個人，每一輪給予n-1個人{1,2,5}個，使得最後大家個數相同，求最少輪數
:::
- 想法
:::info
- 每輪可給n-1人{1,2,5}個，相當於可以收回其中一人{1,2,5}個
- 因為有"+1"的選項，因此最後的個數可以是任何數
- 考慮所有人與最小值的差值
- ex. {2,3,7}最小值為2, 差值為{0,1,5}
- 第一輪, 第三位-5 -> {0,1,0}
- 第二輪, 第二位-1 -> {0,0,0}
- 因此最少需要2輪
- 例外 {2,6,6}最小值為2, 差值為{0,4,4}
1. 由上述方法
- 第二輪, 第二位-2 -> {0,2,4}
- 第二輪, 第二位-2 -> {0,0,4}
- 第三輪, 第三位-2 -> {0,0,2}
- 第四輪, 第三位-2 -> {0,0,0}
- 因此最少需要4輪...嗎?
2. 如果減少最小值=1, 差值為{1,5,5}
- 第一輪, 第一位-1 -> {0,5,5}
- 第二輪, 第二位-5 -> {0,0,5}
- 第三輪, 第三位-5 -> {0,0,0}
- 只需要3輪就可以完成
- 出現例外的狀況是當**差值少於5**時會變成先減掉2, 造成如果需要減掉4就會需要2輪,但其實也可以先把最小值減1, 再減5, 雖然一樣是兩輪, 但如果出現多個同樣差值一來一往就會需要更多輪
- 因此還需要考慮 $max(最小值-4, 0)$到最小值的狀況
- ex. 最小值為2時需要考慮{2,1,0}三種狀況
- ex. 最小值為7時需要考慮{7,6,5,4,3}五種狀況
:::

int equal(int arr_count, int* arr) {
    
    // find mininum
    int min = arr[0];
    for (int i = 0; i < arr_count; i++) {
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    
    //calc difference
    int diff[arr_count];
    int possibility[5] = {-1};
    for (int j = min; j >= ((min-4 > 0) ? (min-4):0); j--) {
        long count = 0;
        for (int i = 0; i < arr_count; i++) {
            diff[i] = arr[i] - j;
            count += diff[i]/5;     //-5
            count += (diff[i]%5)/2; //-2
            count += (diff[i]%5)%2; //-1
        }
        possibility[j%5] = count;
    }
    
    int ans = possibility[0];
    for (int i = 1; i < 5; i++) {
        if (possibility[i] > 0 && possibility[i] < (unsigned)ans)
            ans = possibility[i];
    }
    return ans;
}

- 分析
`Note: Test Case 15沒有過...`
- 時間複雜度: $O(n)$
- 空間複雜度

##
- 題目

- 想法
:::info
:::

- 分析
- 時間複雜度
- 空間複雜度