Hey!
I’ve been trying to come up with a good DP solution to this problem with no luck,
Can someone please share a solution for this?
Variant 17.1.2 - max number of times that lead could change
foo
#1
0 Likes
carlshen
#2
Hi foo,
Don’t be panic, it’s really changeling 
Before sharing solution, I want to share my approach, please correct me if I’m wrong.
Problem
Given an array of positive integers that represents possible points a team could score in an individual play. Now there are two teams play against each other. Their final scores are S and S’. How would you compute the maximum number of times the team that leads could have changed?
For example, if S=10 and S’=6. The lead could have changed 4 times:
Team 1 scores 2, then Team 2 scores 3 (lead change);
Team 1 scores 2 (lead change), Team 2 score 0 (no lead change);
Team 1 scores 0, Team 2 scores 3 (lead change);
Team 1 scores 3, Team 2 scores 0 (lead change);
Team 1 scores 3, Team 2 scores 0 (no lead change).
Analysis
Our target here is to find the maximum number of lead changes. So I let dp[i][j] denote maximum number of lead changes when team 1 scores i, team 2 scores j. For example, dp[2][0] means when team 1 scores 2 and team 2 scores 0, and the value is 1.
To find the maximum changes, we need to consider when it will change? For example, let’s say in the last round, team 1 scores 2 and team 2 scores 3, while enumerating the score, we get 2, if we pick 2, which means the result will become 4 : 3, the lead change.
You may probably find that we’ve already observed the recurrence how to count the lead change! We first need to fetch the last round score, then need to compare whether it could change the lead. Each time we enumerate a score from the score list of [2, 3, 7], we need to look up our table dp[i - score][j]. If i - score < j and i < j and dp[i - score][j] >= dp[i][j] then it will change (we need to plus one). But wait a second, you still need to consider when the lead won’t change. It’s sort of trivial.
After that, if you’ve finished 17.1 variant 1, you may probably know after team 1, we need to calculate team2 as while. 
Below is my solution, I don’t know whether it is a good way to share specific solution in our forum, if @tsunghsienlee finds it’s not appropriate, please let me know.
2 Likes
tejasvi88
#3
@carlshen Can you please reupload CountLeadChange.java? The repository seems to be deleted/private.
0 Likes