Участник:Novruzov.sb/Minimum Cost to Merge Stones

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/minimum-cost-to-merge-stones/

C++

class Solution {
public:
    bool incr_partition(int part[], int size, int step, int end) {
        if (end < 1) {
          return false;
        }
        part[size-1] += step;
        if (part[size-1] >= end) {
            if (size == 1) {
                return false;
            }
            bool ret = incr_partition(part, size-1, step, end-1);
            if (ret) {
                part[size-1] = part[size-2] + 1;
            }
            return ret;
        }
        return true;
    }
 
    int mergeStones(vector<int>& stones, int K) {
        int N = stones.size();
        if (K != 2 and N % (K-1) != 1) {
            return -1;
        }
        int memo[N+1][N+1];
        for (int i = 0; i < N; i++) {
            memo[i][i+1] = 0;
        }
        int subsize = K;
        int end;
        int partitions[K-1];
        bool cont;
        int min_cost, cost;
        int max_cost = 1000000;
        while (subsize <= N) {
            for(int i = 0; i < N - subsize + 1; ++i) {
                end = i + subsize;
                for (int j = 0; j < K-1; j++) {
                    partitions[j] = i+j+1;
                }
                cont = true;
                min_cost = max_cost;
                while (cont) {
                    cost = memo[i][partitions[0]] + memo[partitions[K-2]][end];
                    for (int j = 0; j < K-2; j++) {
                        cost += memo[partitions[j]][partitions[j+1]];
                    }
                    for (int j = i; j < end; j++) {
                        cost += stones[j];
                    }
                    if (cost < min_cost) {
                        min_cost = cost;
                    }
                    cont = incr_partition(partitions, K-1, K-1, end);
                }
                memo[i][end] = min_cost;
            }
            subsize += K-1;
        }
        return memo[0][N];
    }
};