// https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/

​

using System;

​

public class Program

{

    // this is not the DP solution

    // see below for the DP solution

    public static int MinDifficultyOfJobSchedule(int[] jobDifficulties, int days, int jdStartIdx = 0)

    {

        if (jobDifficulties.Length < days) return -1; // ensure we have enough jobs for the days (at least 1 job per day is the requirement)

        int dayDifficulty = 0;

        int remainingDaysDifficultySum = 0;

        int jobDifficulty = 0;

        // here we are going to get all possible combinations of n jobs scheduled for d days

        // will start with 1 job on day 1 and adding 1 job at a time on day 1 but leaving enough jobs to have 1 job per day for the rest of the days

        // will use recursion for the remaining jobs to be scheduled for the remaining days to get its minimum difficulty

        for (int i = jdStartIdx; i < jobDifficulties.Length - days + 1; i++)

        {

            dayDifficulty = Math.Max(dayDifficulty, jobDifficulties[i]);

            if (days > 1)

            {

                remainingDaysDifficultySum = MinDifficultyOfJobSchedule(jobDifficulties, days - 1, i + 1);

            }

            Console.WriteLine($"days={days}, jdStartIdx={jdStartIdx}, i={i}, dayDifficulty={dayDifficulty}, remainingDaysDifficultySum={remainingDaysDifficultySum}");

            if (jobDifficulty == 0) jobDifficulty = dayDifficulty + remainingDaysDifficultySum;

            else jobDifficulty = Math.Min(jobDifficulty, dayDifficulty + remainingDaysDifficultySum);

        }

        return jobDifficulty;

    }

​

    // this is the DP solution

    // we are storing the remaining days difficulty sum at _dp[i,j]

    // where i is the remaining days and j is the starting index of the remaining job difficulties to schedule

    private static int[,] _dp;

    public static int MinDifficultyOfJobScheduleWithDP(int[] jobDifficulties, int days)

    {

        if (jobDifficulties.Length < days) return -1; // ensure we have enough jobs for the days (at least 1 job per day is the requirement)

        _dp = new int[days, jobDifficulties.Length];

        return MinDifficultyOfJobScheduleWithDP_R(jobDifficulties, days);

    }

    private static int MinDifficultyOfJobScheduleWithDP_R(int[] jobDifficulties, int days, int jdStartIdx = 0)

    {   

        int dayDifficulty = 0;

        int remainingDaysDifficultySum = 0;

        int jobDifficulty = 0;

        // here we are going to get all possible combinations of n jobs scheduled for d days

        // will start with 1 job on day 1 and adding 1 job at a time on day 1 but leaving enough jobs to have 1 job per day for the rest of the days

        // will use recursion for the remaining jobs to be scheduled for the remaining days

        for (int i = jdStartIdx; i < jobDifficulties.Length - days + 1; i++)

        {

            dayDifficulty = Math.Max(dayDifficulty, jobDifficulties[i]);

            bool lookedUp = false;

            if (days > 1)

            {

                if (_dp[(days - 1) - 1, i + 1] > 0)

                {

                    lookedUp = true;

                    remainingDaysDifficultySum = _dp[(days - 1) -1, i + 1];

                }

                else

                {

                    remainingDaysDifficultySum = MinDifficultyOfJobScheduleWithDP_R(jobDifficulties, days - 1, i + 1);

                    _dp[(days - 1) -1, i + 1] = remainingDaysDifficultySum;

                }

            }

            Console.WriteLine($"days={days}, jdStartIdx={jdStartIdx}, i={i}, dayDifficulty={dayDifficulty}, remainingDaysDifficultySum={remainingDaysDifficultySum}{(lookedUp ? "(looked up)" : "")}");

            if (jobDifficulty == 0) jobDifficulty = dayDifficulty + remainingDaysDifficultySum;

            else jobDifficulty = Math.Min(jobDifficulty, dayDifficulty + remainingDaysDifficultySum);

        }

        return jobDifficulty;

    }

​

    public static void Main()

    {

        int[] jobDifficulties = new int[] {6, 5, 4, 3, 2, 1};

        int days = 2;

        Console.WriteLine($"input: jobDifficulties=[{string.Join(',', jobDifficulties)}], days={days}");

        Console.WriteLine($"min difficulty: {MinDifficultyOfJobSchedule(jobDifficulties, days)}");

​

        Console.WriteLine();

        jobDifficulties = new int[] {9, 9, 9};

        days = 4;

        Console.WriteLine($"input: jobDifficulties=[{string.Join(',', jobDifficulties)}], days={days}");

        Console.WriteLine($"min difficulty: {MinDifficultyOfJobSchedule(jobDifficulties, days)}");

​

        Console.WriteLine();

        jobDifficulties = new int[] {1, 1, 1};

        days = 3;

        Console.WriteLine($"input: jobDifficulties=[{string.Join(',', jobDifficulties)}], days={days}");

        Console.WriteLine($"min difficulty: {MinDifficultyOfJobSchedule(jobDifficulties, days)}");

​

        Console.WriteLine();

        jobDifficulties = new int[] {6, 5, 4, 3, 2, 1};

        days = 4;

        Console.WriteLine($"input: jobDifficulties=[{string.Join(',', jobDifficulties)}], days={days}");

        Console.WriteLine($"min difficulty: {MinDifficultyOfJobScheduleWithDP(jobDifficulties, days)}");

}

}