# 2020q3 sysprog Homework8 (quiz8)
###### tags: `sysprog`
contributed by < `sciyen` >

[Toc]

## Q1 [LeetCode 1494. Parallel Courses II](https://leetcode.com/problems/parallel-courses-ii/)

#include <string.h>                                                                                                                                           
#include <limits.h>

#define min(a, b) (((a) < (b)) ? (a) : (b))
static void solve(int i, int s, int k, int n, int s0, int s1, int *dp)
{
    if ((k == 0) || (i == n)) {
        dp[s0 | s] = min(dp[s0 | s], dp[s0] + 1);
        return;
    }

    solve(i + 1, s, k, n, s0, s1, dp);

    if ((s1 >> i) & 1)
        solve(i + 1, s | 1 << i, k - 1, n, s0, s1, dp);
}

int minNumberOfSemesters(int n,
                         int **dependencies,
                         int dependenciesSize,        // Number of dependencies
                         int *dependenciesColSize,
                         int k)
{
    // Use each bit to represent classes, so the size is 2^n
    // Create a map that indicate class `index`'s dependencies in the form of bits
    const size_t cap = 1 << n;
    int pre[cap];
    
    // Reset all array element to 0
    memset(pre, 0, sizeof(pre));
    for (int i = 0; i < dependenciesSize; i++)
        // Because class id start from 1, so we add `-1` while indexing
        // `|=` set `i` class's all dependencies to 1
        pre[dependencies[i][1] - 1] |= 1 << (dependencies[i][0] - 1);

    // Initialize the map that restore the minimal answer of each class
    int dp[cap];
    for (int i = 1; i < cap; i++)
        dp[i] = INT_MAX;
    dp[0] = 0;

    for (int s0 = 0; s0 < cap; s0++) {
        if (dp[s0] == INT_MAX)
            continue;

        int s1 = 0;
        for (int i = 0; i < n; i++)
            if (!((s0 >> i) & 1) && ((pre[i] & s0) == pre[i]))
                s1 |= 1 << i;

        solve(0, 0, k, n, s0, s1, dp);
    }

    return dp[cap - 1];
}