Stone Game (Optimal Strategy)

🎯

Stone Game (Optimal Strategy)

mediumDPAmazonGoogle

Imagine two players taking turns to pick stones from either end of a row of piles, each trying to maximize their own total stones collected. How can one determine if the first player can always win assuming both play optimally?

💡 This problem is a classic example of game theory combined with dynamic programming. Beginners often struggle because it requires thinking ahead about opponent moves and understanding how to model the problem as intervals with optimal substructure.

📋

Problem Statement

Given an array piles where piles[i] represents the number of stones in the i-th pile, two players (Alex and Lee) take turns picking a pile from either the start or the end of the row. Both players play optimally. Return true if Alex can win (get more stones than Lee), otherwise false.

2 ≤ piles.length ≤ 500piles.length is even1 ≤ piles[i] ≤ 500

💡

Example

Input"[5,3,4,5]"

Outputtrue

Alex picks 5 from the start, Lee picks 5 from the end, Alex picks 4, Lee picks 3. Alex total = 9, Lee total = 8, so Alex wins.

• All piles have the same number of stones → Alex always wins or ties
• Only two piles → Alex picks the larger pile and wins
• Piles with increasing values → Alex picks optimally to maximize gain
• Piles with decreasing values → Alex picks optimally to maximize gain

🔁

Why DP?

Why greedy fails:

A greedy approach that always picks the pile with the maximum stones at the current turn fails because it ignores future consequences. For example, picking the largest pile now may leave the opponent with a better choice next turn, leading to a loss.

DP state:

dp[i][j] represents the maximum difference in stones the current player can achieve over the opponent when considering piles from index i to j.

Recurrence:dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])

The current player chooses either the left or right pile, then the opponent plays optimally on the remaining piles. The difference is updated accordingly.

⚠️

Common Mistakes

Forgetting to subtract opponent's score in recursion

Incorrect results because the opponent's optimal response is ignored

✅ Subtract dp of opponent's turn from current pile value

Not memoizing results leading to TLE

Exponential runtime and timeouts on large inputs

✅ Use a memo table to cache computed intervals

Incorrect base case handling when i == j

Wrong results or runtime errors due to missing base case

✅ Return piles[i] when interval reduces to one pile

Filling dp table in wrong order in tabulation

Using uninitialized dp values leads to wrong answers

✅ Fill dp diagonally from smaller intervals to larger intervals

Assuming greedy approach works

Fails on test cases where picking largest pile first is suboptimal

✅ Use DP to consider all possibilities and opponent's optimal play

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive nature and the decision-making process at each turn, even though it is inefficient.

Intuition

At each turn, the player chooses either the leftmost or rightmost pile, then the opponent plays optimally on the remaining piles. We recursively compute the best outcome for the current player.

Algorithm

1. Define a recursive function that returns the maximum score difference the current player can achieve from piles i to j.
2. If i == j, return piles[i] because only one pile is left.
3. Otherwise, recursively compute the result if the player picks the left pile or the right pile.
4. Return the maximum of these two choices.

💡 The recursion is straightforward but leads to repeated calculations of the same intervals, making it inefficient.

Recurrence:dp(i,j) = max(piles[i] - dp(i+1,j), piles[j] - dp(i,j-1))

</>

Code

def stoneGame(piles):
    def dfs(i, j):
        if i == j:
            return piles[i]
        left = piles[i] - dfs(i + 1, j)
        right = piles[j] - dfs(i, j - 1)
        return max(left, right)
    return dfs(0, len(piles) - 1) > 0

# Driver code
if __name__ == '__main__':
    print(stoneGame([5,3,4,5]))  # True

Line Notes

def dfs(i, j):Defines the recursive helper to compute max difference for interval i to j

if i == j:Base case: only one pile left, current player takes it

left = piles[i] - dfs(i + 1, j)Choose left pile, subtract opponent's best response

right = piles[j] - dfs(i, j - 1)Choose right pile, subtract opponent's best response

return max(left, right)Pick the choice that maximizes current player's advantage

return dfs(0, len(piles) - 1) > 0Check if first player can achieve positive difference

public class Solution {
    public boolean stoneGame(int[] piles) {
        return dfs(piles, 0, piles.length - 1) > 0;
    }
    private int dfs(int[] piles, int i, int j) {
        if (i == j) return piles[i];
        int left = piles[i] - dfs(piles, i + 1, j);
        int right = piles[j] - dfs(piles, i, j - 1);
        return Math.max(left, right);
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.stoneGame(new int[]{5,3,4,5})); // true
    }
}

Line Notes

public boolean stoneGame(int[] piles)Entry point to check if first player can win

return dfs(piles, 0, piles.length - 1) > 0;Start recursion on full interval and check positive difference

if (i == j) return piles[i];Base case: only one pile left

int left = piles[i] - dfs(piles, i + 1, j);Pick left pile and subtract opponent's best response

int right = piles[j] - dfs(piles, i, j - 1);Pick right pile and subtract opponent's best response

return Math.max(left, right);Choose the better option for current player

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int dfs(vector<int>& piles, int i, int j) {
        if (i == j) return piles[i];
        int left = piles[i] - dfs(piles, i + 1, j);
        int right = piles[j] - dfs(piles, i, j - 1);
        return max(left, right);
    }
    bool stoneGame(vector<int>& piles) {
        return dfs(piles, 0, piles.size() - 1) > 0;
    }
};

int main() {
    Solution sol;
    vector<int> piles = {5,3,4,5};
    cout << boolalpha << sol.stoneGame(piles) << endl; // true
    return 0;
}

Line Notes

int dfs(vector<int>& piles, int i, int j)Recursive function to compute max difference in interval i to j

if (i == j) return piles[i];Base case: only one pile left

int left = piles[i] - dfs(piles, i + 1, j);Choose left pile and subtract opponent's best response

int right = piles[j] - dfs(piles, i, j - 1);Choose right pile and subtract opponent's best response

return max(left, right);Pick the better choice for current player

return dfs(piles, 0, piles.size() - 1) > 0;Check if first player can win

var stoneGame = function(piles) {
    function dfs(i, j) {
        if (i === j) return piles[i];
        let left = piles[i] - dfs(i + 1, j);
        let right = piles[j] - dfs(i, j - 1);
        return Math.max(left, right);
    }
    return dfs(0, piles.length - 1) > 0;
};

console.log(stoneGame([5,3,4,5])); // true

Line Notes

function dfs(i, j)Recursive helper to compute max difference for interval i to j

if (i === j) return piles[i];Base case: only one pile left

let left = piles[i] - dfs(i + 1, j);Pick left pile and subtract opponent's best response

let right = piles[j] - dfs(i, j - 1);Pick right pile and subtract opponent's best response

return Math.max(left, right);Choose the better option for current player

return dfs(0, piles.length - 1) > 0;Check if first player can win

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each call branches into two, leading to exponential calls. The recursion depth is at most n.

💡 For n=20, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing the same intervals by caching results, drastically improving efficiency while preserving the recursive intuition.

Intuition

Store results of subproblems dp[i][j] so that when the same interval is encountered again, return the cached result instead of recomputing.

Algorithm

1. Initialize a 2D memo array to store results for intervals.
2. Modify the recursive function to check memo before computing.
3. If result exists in memo, return it immediately.
4. Otherwise, compute recursively and store the result in memo.

💡 Memoization transforms exponential recursion into polynomial time by remembering past results.

Recurrence:dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])

</>

Code

def stoneGame(piles):
    n = len(piles)
    memo = [[None]*n for _ in range(n)]
    def dfs(i, j):
        if i == j:
            return piles[i]
        if memo[i][j] is not None:
            return memo[i][j]
        left = piles[i] - dfs(i + 1, j)
        right = piles[j] - dfs(i, j - 1)
        memo[i][j] = max(left, right)
        return memo[i][j]
    return dfs(0, n - 1) > 0

# Driver code
if __name__ == '__main__':
    print(stoneGame([5,3,4,5]))  # True

Line Notes

memo = [[None]*n for _ in range(n)]Create memo table to cache results for intervals

if memo[i][j] is not None:Return cached result if available to avoid recomputation

memo[i][j] = max(left, right)Store computed result for interval i to j

return dfs(0, n - 1) > 0Check if first player can win based on computed difference

public class Solution {
    private Integer[][] memo;
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        memo = new Integer[n][n];
        return dfs(piles, 0, n - 1) > 0;
    }
    private int dfs(int[] piles, int i, int j) {
        if (i == j) return piles[i];
        if (memo[i][j] != null) return memo[i][j];
        int left = piles[i] - dfs(piles, i + 1, j);
        int right = piles[j] - dfs(piles, i, j - 1);
        memo[i][j] = Math.max(left, right);
        return memo[i][j];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.stoneGame(new int[]{5,3,4,5})); // true
    }
}

Line Notes

private Integer[][] memo;Memo table to store results for intervals

if (memo[i][j] != null) return memo[i][j];Return cached result if computed before

memo[i][j] = Math.max(left, right);Cache the computed max difference for interval

return dfs(piles, 0, n - 1) > 0;Determine if first player can win

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class Solution {
    vector<vector<int>> memo;
public:
    int dfs(vector<int>& piles, int i, int j) {
        if (i == j) return piles[i];
        if (memo[i][j] != INT_MIN) return memo[i][j];
        int left = piles[i] - dfs(piles, i + 1, j);
        int right = piles[j] - dfs(piles, i, j - 1);
        memo[i][j] = max(left, right);
        return memo[i][j];
    }
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        memo.assign(n, vector<int>(n, INT_MIN));
        return dfs(piles, 0, n - 1) > 0;
    }
};

int main() {
    Solution sol;
    vector<int> piles = {5,3,4,5};
    cout << boolalpha << sol.stoneGame(piles) << endl; // true
    return 0;
}

Line Notes

vector<vector<int>> memo;2D memo table to cache results

if (memo[i][j] != INT_MIN) return memo[i][j];Return cached result if available

memo.assign(n, vector<int>(n, INT_MIN));Initialize memo with sentinel values

memo[i][j] = max(left, right);Store computed max difference for interval

var stoneGame = function(piles) {
    const n = piles.length;
    const memo = Array.from({length: n}, () => Array(n).fill(null));
    function dfs(i, j) {
        if (i === j) return piles[i];
        if (memo[i][j] !== null) return memo[i][j];
        const left = piles[i] - dfs(i + 1, j);
        const right = piles[j] - dfs(i, j - 1);
        memo[i][j] = Math.max(left, right);
        return memo[i][j];
    }
    return dfs(0, n - 1) > 0;
};

console.log(stoneGame([5,3,4,5])); // true

Line Notes

const memo = Array.from({length: n}, () => Array(n).fill(null));Initialize memo table with nulls

if (memo[i][j] !== null) return memo[i][j];Return cached result if computed

memo[i][j] = Math.max(left, right);Cache computed max difference for interval

return dfs(0, n - 1) > 0;Check if first player can win

⏱

Complexity

TimeO(n^2)

SpaceO(n^2) for memo + O(n) recursion stack

Each interval i,j is computed once and stored, reducing exponential calls to quadratic.

💡 For n=500, this means about 250,000 computations, which is efficient enough.

Interview Verdict: Accepted

Memoization makes the solution efficient and practical for interview constraints.

🧠

Bottom-Up DP (Tabulation)

💡 Tabulation builds the solution iteratively from smaller intervals to larger ones, avoiding recursion and making the process explicit and often easier to debug.

Intuition

Start with intervals of length 1 (single piles), then solve for length 2, 3, ..., up to n, using previously computed results.

Algorithm

1. Initialize a 2D dp array where dp[i][i] = piles[i] for all i.
2. Iterate over interval lengths from 2 to n.
3. For each interval [i, j], compute dp[i][j] using the recurrence.
4. Return true if dp[0][n-1] > 0, meaning first player can win.

💡 Tabulation explicitly shows the order of computation and avoids recursion overhead.

Recurrence:dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])

</>

Code

def stoneGame(piles):
    n = len(piles)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = piles[i]
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
    return dp[0][n-1] > 0

# Driver code
if __name__ == '__main__':
    print(stoneGame([5,3,4,5]))  # True

Line Notes

dp = [[0]*n for _ in range(n)]Initialize dp table for intervals

dp[i][i] = piles[i]Base case: single pile intervals

for length in range(2, n+1)Iterate over interval lengths

dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])Apply recurrence to compute dp for interval

return dp[0][n-1] > 0Check if first player can win from full interval

public class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = piles[i];
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] > 0;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.stoneGame(new int[]{5,3,4,5})); // true
    }
}

Line Notes

int[][] dp = new int[n][n];Create dp table for intervals

dp[i][i] = piles[i];Base case for single pile intervals

for (int length = 2; length <= n; length++)Loop over interval lengths

dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);Compute dp using recurrence

return dp[0][n - 1] > 0;Check if first player can win

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) dp[i][i] = piles[i];
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] > 0;
    }
};

int main() {
    Solution sol;
    vector<int> piles = {5,3,4,5};
    cout << boolalpha << sol.stoneGame(piles) << endl; // true
    return 0;
}

Line Notes

vector<vector<int>> dp(n, vector<int>(n, 0));Initialize dp table for intervals

dp[i][i] = piles[i];Base case for single pile intervals

for (int length = 2; length <= n; length++)Iterate over interval lengths

dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);Apply recurrence to compute dp

return dp[0][n - 1] > 0;Check if first player can win

var stoneGame = function(piles) {
    const n = piles.length;
    const dp = Array.from({length: n}, () => Array(n).fill(0));
    for (let i = 0; i < n; i++) dp[i][i] = piles[i];
    for (let length = 2; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            let j = i + length - 1;
            dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
        }
    }
    return dp[0][n - 1] > 0;
};

console.log(stoneGame([5,3,4,5])); // true

Line Notes

const dp = Array.from({length: n}, () => Array(n).fill(0));Initialize dp table for intervals

dp[i][i] = piles[i];Base case for single pile intervals

for (let length = 2; length <= n; length++)Iterate over interval lengths

dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);Apply recurrence to compute dp

return dp[0][n - 1] > 0;Check if first player can win

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

We fill an n by n table once, each cell computed in O(1).

💡 For n=500, this is about 250,000 operations, efficient for interviews.

Interview Verdict: Accepted

Tabulation is often preferred for clarity and iterative control.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoization or tabulation are the best choices for coding in interviews due to efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down DP with Memoization	O(n^2)	O(n^2) memo + O(n) recursion stack	Possible but less likely	Yes	Good choice to code
3. Bottom-Up DP (Tabulation)	O(n^2)	O(n^2)	No	Yes	Preferred for clarity and iterative control

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and confirm understanding.Step 2: Present brute force recursion to show problem structure.Step 3: Introduce memoization to optimize recursion.Step 4: Explain bottom-up tabulation as an iterative alternative.Step 5: Discuss time and space complexities and possible optimizations.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of game theory, recursion, DP optimization, and ability to write clean, correct code.

Common Follow-ups

• What if piles length is odd? → Adjust logic or prove first player advantage.
• Can we optimize space? → Discuss space optimization possibilities.
• How to reconstruct the moves? → Store choices during DP computation.
• What if players don't play optimally? → Problem changes, no DP guarantee.

💡 These follow-ups test deeper understanding and ability to adapt solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves two players taking turns; 2) Choices are from intervals or ends; 3) Both players play optimally; 4) Need to predict winner or max score.

Signature Phrases

two players take turnsboth play optimallypicking from either end

NOT This Pattern When

Problems with greedy solutions or no opponent strategy are different.

Similar Problems

Predict the Winner - similar interval game DPBurst Balloons - interval DP with different scoringRemove Boxes - complex interval DP with grouping

Practice

1. You need to find the cheapest cost to travel from a source city to a destination city with at most K stops, given a list of flights with costs. Which algorithmic approach guarantees finding the optimal solution efficiently under these constraints?

easy

A. Greedy algorithm using Dijkstra's shortest path without modification

B. Topological sort followed by single pass relaxation of edges

C. Simple depth-first search exploring all paths without pruning

D. Dynamic programming using a bottom-up approach iterating over stops

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the cheapest flight with at most K stops, which limits path length and requires considering multiple paths.

2. Step 2: Identify suitable algorithm

   Greedy Dijkstra fails because it doesn't limit stops; DFS is exponential; topological sort requires DAG which flights graph may not be. Bottom-up DP iterates over stops and relaxes edges, guaranteeing optimal cost within K stops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bottom-up DP with stops limit ensures optimal solution [OK]

Hint: DP with stops limit ensures optimal cost [OK]

Common Mistakes:

• Using Dijkstra without stop limit
• Trying DFS without pruning
• Assuming DAG for topological sort

2. You are given an n x n integer matrix. You want to find a path from the top row to the bottom row such that you move one step down each time, and at each step you can move to the same column, the column to the left, or the column to the right. The goal is to minimize the sum of the values along this path. Which algorithmic approach guarantees finding the minimum sum efficiently?

easy

A. Greedy algorithm that picks the minimum adjacent value at each step

B. Sorting each row and picking the smallest values independently

C. Depth-first search exploring all paths without memoization

D. Dynamic programming that builds solutions row by row using previous row results

Solution

1. Step 1: Understand the problem constraints

   The problem requires considering all possible paths moving down and diagonally, which suggests overlapping subproblems and optimal substructure.

2. Step 2: Identify the suitable algorithm

   Dynamic programming fits because it efficiently computes minimum sums for each cell based on the previous row's results, avoiding redundant calculations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy and sorting fail to consider future steps; DFS without memoization is exponential [OK]

Hint: DP uses previous row results to build solutions [OK]

Common Mistakes:

• Thinking greedy or sorting per row suffices
• Ignoring overlapping subproblems

3. Consider the following bottom-up DP code for the Strange Printer problem. What is the final returned value when the input string is "aba"?

easy

A. 3

B. 4

C. 1

D. 2

Solution

1. Step 1: Compress input string "aba"

   Compression does not change string since no consecutive duplicates: s = "aba", n=3.

2. Step 2: Trace dp table filling

   Base cases: dp[0][0]=1, dp[1][1]=1, dp[2][2]=1. For length=2: - dp[0][1]: dp[0][0]+1=2, s[0]!=s[1], so dp[0][1]=2 - dp[1][2]: dp[1][1]+1=2, s[1]!=s[2], so dp[1][2]=2 For length=3: - dp[0][2]: dp[0][1]+1=3 Check k=0: s[0]==s[2] ('a'=='a'), dp[0][0]+dp[1][1]=1+1=2 < 3, so dp[0][2]=2

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches known minimal turns for "aba" [OK]

Hint: Check dp merging when s[k] == s[j] reduces turns [OK]

Common Mistakes:

• Forgetting to merge intervals when characters match

4. The following code attempts to solve the Unique Paths II problem using a space-optimized DP approach. Identify the line containing the subtle bug that causes incorrect results when the start cell is an obstacle.

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [0]*n
    dp[0] = 1  # Bug here
    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[j] = 0
            else:
                if j > 0:
                    dp[j] += dp[j-1]
    return dp[-1]

medium

A. Line 4: dp[0] = 1 # Initialization without checking start cell obstacle

B. Line 7: if obstacleGrid[i][j] == 1: dp[j] = 0

C. Line 10: if j > 0: dp[j] += dp[j-1]

D. Line 3: dp = [0]*n

Solution

1. Step 1: Check initialization of dp[0]

   dp[0] is set to 1 unconditionally, ignoring if start cell is blocked.

2. Step 2: Consequence of bug

   If start cell is an obstacle, dp[0] should be 0, otherwise paths count is incorrectly non-zero.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Proper initialization must consider obstacleGrid[0][0] [OK]

Hint: Start cell obstacle must set dp[0] to 0 [OK]

Common Mistakes:

• Ignoring start cell obstacle
• Not zeroing dp on obstacles
• Misusing dp[j-1] before update

5. Suppose the problem is modified so that you can take unlimited flights (reuse edges) but still want the cheapest price within K stops. Which modification to the bottom-up DP approach correctly handles this variant?

hard

A. Use Bellman-Ford algorithm with K+1 iterations allowing edge reuse in each iteration

B. Switch to Dijkstra's algorithm since unlimited reuse removes stop constraints

C. Modify DP to allow updating curr[v] multiple times per iteration by relaxing edges repeatedly until no changes

D. Use the same bottom-up DP but increase iterations to K+1 without changes

Solution

1. Step 1: Understand the unlimited reuse variant

   Unlimited reuse means cycles are allowed, so shortest path with stop constraints resembles Bellman-Ford relaxation over K+1 iterations.

2. Step 2: Identify correct algorithm

   Bellman-Ford naturally handles edge reuse and negative cycles (if any), iterating K+1 times to relax edges, matching problem constraints.

3. Step 3: Why other options fail

   Use the same bottom-up DP but increase iterations to K+1 without changes ignores edge reuse effect; Switch to Dijkstra's algorithm since unlimited reuse removes stop constraints ignores stop constraints; Modify DP to allow updating curr[v] multiple times per iteration by relaxing edges repeatedly until no changes suggests repeated relaxation within iteration, which is inefficient and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Bellman-Ford with K+1 iterations handles unlimited reuse correctly [OK]

Hint: Bellman-Ford handles edge reuse with K+1 relaxations [OK]

Common Mistakes:

• Using Dijkstra ignoring stops
• Not increasing iterations
• Trying repeated relaxations inside iteration