12. Arithmetic Slices II - Subsequence

Problem: Find the number of arithmetic subsequences with at least 3 elements.
Approach: DP. `dp[i]` = a hashmap where `dp[i][diff]` stores the count of arithmetic subsequences ending at index `i` with common difference `diff` and length at least 2.
State Transition:
- For each `nums[i]`:
  - For each `nums[j]` where $j < i$:
    - Calculate `diff = nums[i] - nums[j]`.
    - `dp[i][diff]` is incremented by `dp[j][diff]` (subsequences of length $\ge 2$ ending at `j` extended by `nums[i]`) + 1 (new subsequence of length 2: `nums[j], nums[i]`).
    - `ans` is incremented by `dp[j][diff]` (these are subsequences of length $\ge 3$).

from collections import defaultdict

def numberOfArithmeticSlices(nums: list[int]) -> int:
    n = len(nums)
    if n < 3:
        return 0

    total_count = 0
    # dp[i] is a hashmap: {diff: count of arithmetic subsequences ending at i with this diff}
    dp = [defaultdict(int) for _ in range(n)]

    for i in range(n):
        for j in range(i):
            diff = nums[i] - nums[j]
            # Handle potential overflow if using raw diff directly for large numbers
            # In Python, integers handle arbitrary size, so it's fine.
            # If diff is too big for a dict key, one might map it.
            
            # Number of subsequences of length >= 2 ending at j with this diff
            count_j_diff = dp[j][diff]
            
            # Extend subsequences of length >= 2 ending at j with nums[i]
            # This adds count_j_diff new subsequences of length >= 3
            total_count += count_j_diff
            
            # Add current pair (nums[j], nums[i]) as a new subsequence of length 2
            # And add all extended subsequences from dp[j][diff]
            dp[i][diff] += count_j_diff + 1
            
    return total_count

13. Minimum Difficulty of a Job Schedule

Problem: Schedule jobs over `d` days. Each day, complete at least one job. The difficulty of a day is the max difficulty of jobs done that day. Minimize total difficulty.
Approach: DP. `dp[i][j]` = min difficulty to schedule first `j` jobs in `i` days.
State Transition:
- `dp[i][j] = min(dp[i-1][k] + max_diff(jobs[k+1...j]))` for $k$ from $i-2$ to $j-1$.
- `max_diff(jobs[k+1...j])` is the maximum difficulty for jobs done on day `i`.
- Base cases: `dp[1][j]` = max difficulty of `jobs[0...j-1]`.

def minDifficulty(jobDifficulty: list[int], d: int) -> int:
    n = len(jobDifficulty)
    if n < d:
        return -1 # Not enough jobs for each day

    # dp[i][j] = min difficulty to schedule first j jobs in i days
    # Initialize with infinity
    dp = [[float('inf')] * (n + 1) for _ in range(d + 1)]

    # Base case: 0 jobs, 0 days -> 0 difficulty
    dp[0][0] = 0 

    # For day 1 (i=1):
    # dp[1][j] is the max difficulty of jobs[0...j-1]
    max_d = 0
    for j in range(1, n + 1):
        max_d = max(max_d, jobDifficulty[j-1])
        dp[1][j] = max_d
    
    for i in range(2, d + 1): # Number of days
        for j in range(i, n + 1): # Number of jobs (must be at least i)
            # To schedule j jobs in i days, the last day (day i) must handle jobs from k to j-1
            # The previous i-1 days must handle k jobs
            # k must be at least i-1 (to accommodate i-1 days) and less than j
            
            current_day_max_diff = 0
            for k_prev_jobs in range(j - 1, i - 2, -1): # k_prev_jobs from j-1 down to i-1
                # jobs[k_prev_jobs] ... jobs[j-1] are done on day i