Buying Candies

Logical Breakdown

• [ ] Subproblem Identification:
• [ ] Optimal Substructure:
• [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
• [ ] Optimization: (Matrix Exponentiation if 'A' is huge)

---

Mathematical Rigor

State Definition

Let \(dp[i]\) be the state for the \(i\)-th subproblem.

Recurrence Relation

\[ dp[i] = ... \]

---

Visualization

graph TD A["Current State"] --> B["Previous State 1"] A --> C["Previous State 2"]

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Iterative DP	\(O(N)\)	\(O(1)\)

---

Code Reference

package com.dsa.dynamic_programming;

import java.util.*;

/ * Problem: Buying Candies * Group: 11. Dynamic Programming */ / * ============================================================================================ * PROBLEM: Buying Candies * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given arrays A (Candies in packet i) and B (Cost of packet i). * Given integer C (Total Money). * Find max candies you can buy. * Constraint: Unbounded (can buy same packet multiple times). * * --------------------- * 2. Logical Mapping * --------------------- * This is a direct application of the UNBOUNDED KNAPSACK problem. * - Value => A[i] (Number of Candies) * - Weight => B[i] (Cost) * - Capacity => C (Money) * * --------------------- * 3. Implementation Detail * --------------------- * dp[j] = Max candies with money 'j'. * Iterate j from 1 to C. * For each packet i: * if (cost[i] <= j) * dp[j] = max(dp[j], candies[i] + dp[j - cost[i]]) * * Time: O(N * C) * Space: O(C) * * ============================================================================================ */ public class BuyingCandies { public int solve(int A) { // TODO: Implement solution return 0; }

public int solve(int[] candies, int[] costs, int i) {
    return 0;
}

}