- Get link
- Other Apps

### Featured Post

Posted by
Varun
on

- Get link
- Other Apps

Hey there, intrepid coders! Today, we're diving into a piggy bank heist… of the intellectual kind, of course! We'll be using a powerful technique called Dynamic Programming (DP) to crack the code of a mischievous piggy bank and unlock its hidden treasures. Buckle up, because this adventure requires both logic and a dash of mathematical magic.

Imagine a piggy bank with compartments numbered 1 to N. Each compartment holds a certain amount of coins. Your mission is to maximise the total coins you can collect by following these two rules:

- You can only start at compartment 1 and move rightward, collecting all the coins in a compartment before proceeding.
- You can either skip a compartment (earning you 0 coins) or rob a compartment, but robbing two consecutive compartments is forbidden.

This might seem tricky, but DP comes to the rescue! It breaks down the problem into smaller, overlapping subproblems and cleverly stores the solutions, saving you from redundant calculations. Think of it like mapping a treasure hunt – each solution to a subproblem guides you towards the bigger prize.

```
class PiggyBankBreaker {
private final int[] coins; // Array storing coins in each compartment (1-indexed)
private final int[] maxCoins; // DP array to store max achievable coins at each position (0-indexed)
public PiggyBankBreaker(int[] coins) {
this.coins = coins; // Copy original coin values
this.maxCoins = new int[coins.length + 1]; // Allocate DP array with space for starting point (index 0)
}
public int crackPiggyBank() {
// Base case: No coins at starting point
maxCoins[0] = 0;
// Loop through each compartment from index 1 (inclusive)
for (int i = 1; i <= coins.length; i++) {
// Option 1: Rob current compartment + max from 2 positions back (non-consecutive)
int robCurrent;
// Check if robbing current is even possible (avoid accessing coins[-1])
if (i >= 3) {
robCurrent = coins[i - 1] + maxCoins[i - 3];
} else {
// Default to skipping for initial positions where robbing isn't valid
robCurrent = 0;
}
// Option 2: Skip current compartment and take max from previous position (consecutive)
int skipCurrent = maxCoins[i - 1];
// Choose the option that yields more coins
maxCoins[i] = Math.max(robCurrent, skipCurrent);
}
// Return the maximum achievable coins from the last compartment
return maxCoins[coins.length];
}
public static void main(String[] args) {
// Example piggy bank with coins
int[] coins = {2, 3, 1, 4, 5, 7, 10};
PiggyBankBreaker breaker = new PiggyBankBreaker(coins);
int maxLoot = breaker.crackPiggyBank();
System.out.println("Maximum amount you can collect: " + maxLoot);
}
}
```

This Java code solves the piggy bank problem, where you maximise the coins collected while adhering to two rules:

- Start at compartment 1 and move rightward, collecting all coins in each compartment.
- You can either skip or rob a compartment, but not two consecutive compartments.

The code utilises Dynamic Programming (DP) to efficiently solve this problem by breaking it down into smaller, overlapping subproblems. Here's a breakdown of the key aspects:

- The method calculates the maximum coins achievable from any starting point.
- Base case:
`maxCoins[0] = 0`

since no coins are earned before starting. - Loop: Iterates through each compartment (index 1 to length).
- Rob current option:
- Calculates
`robCurrent`

by adding the current coin value (`coins[i - 1]`

) to the maximum coins achievable two positions back (`maxCoins[i - 3]`

). - Fix: A conditional statement (
`i >= 3`

) ensures this calculation only happens for valid positions (avoiding`coins[-1]`

access). - Otherwise,
`robCurrent`

is set to 0, mimicking skipping the compartment for initial positions.

- Calculates
- Skip current option: Simply takes the maximum coins from the previous position (
`maxCoins[i - 1]`

). - Comparison: Chooses the maximum value between
`robCurrent`

and`skipCurrent`

and stores it in`maxCoins[i]`

. This ensures the optimal decision is recorded for future subproblems. - Final result: The last element
`maxCoins[coins.length]`

represents the maximum achievable coins from the starting point (compartment 1).

Algorithmic solution
Code implementation
Coin denomination
Cracking piggy bank puzzle
dynamic programming
Java
Java programming
Money-saving challenge
Optimal change
Problem-solving
Recursive approach

- Get link
- Other Apps

## Comments

## Post a Comment

Please post your valuable suggestions