[PR #632] [CLOSED] Create Dynamic programming Algorithm #1086

New Issue

claunia · 2026-01-29T15:17:29Z

claunia commented

2026-01-29 15:17:29 +00:00

📋 Pull Request Information

Original PR: https://github.com/TheAlgorithms/C/pull/632
Author: @Bhavykapadiya
Created: 10/1/2020
Status: ❌ Closed

Base: master ← Head: patch-1

📝 Commits (1)

0f266df Create Dynamic programming Algorithm

📊 Changes

1 file changed (+39 additions, -0 deletions)

View changed files

➕ Dynamic programming Algorithm (+39 -0)

📄 Description

Objective: In this game, which we will call the coins-in-a-line game, an even number, n, of coins, of various denominations from various countries, are placed in a line. Two players, who we will call Alice and Bob, take turns removing one of the coins from either end of the remaining line of coins. That is, when it is a player’s turn, he or she removes the coin at the left or right end of the line of coins and adds that coin to his or her collection. The player who removes a set of coins with larger total value than the other player wins, where we assume that both Alice and Bob know the value of each coin.

Example:

coins [] = { 6, 9, 1, 2, 16, 8}

trial 1: (players will pick the best option available for them)
coins [] = { 6, 9, 1, 2, 16, 8} , Alice picks 8
coins [] = { 6, 9, 1, 2, 16}, Bob picks 16
coins [] = { 6, 9, 1, 2}, Alice picks 6
coins [] = { 9, 1, 2}, Bob picks 9
coins [] = {1, 2}, Alice picks 2
coins [] = {1}, Bob picks 1
Alice: 8+6+2 =16 Bob: 16+9+1=26 => Alice Lost

So clearly picking up the best in each move is not good for Alice. What else Alice can do to win the game.

trial 2: (Alice thinks about Bob's move, Will discuss the strategy in solution)
coins [] = { 6, 9, 1, 2, 16, 8} , Alice picks 6
coins [] = { 9, 1, 2, 16, 8}, Bob picks 9
coins [] = { 1, 2, 16, 8}, Alice picks 1
coins [] = 2, 16, 8}, Bob picks 8
coins [] = {2, 16}, Alice picks 16
coins [] = {2}, Bob picks 2
Alice: 6+1+16 =23 Bob: 9+8+2=19 => Alice Won

So this time Alice has won. Let's see the solution and discuss what Alice has done to win the game.
Approach:

We will solve this problem using Dynamic programming in Bottom-up manner.

In the example above we have seen that in trail 1 Alice has lost and in trial 2 Alice has won. So clearly picking the best coin available in each move is good option for Alice.

So the question is what Alice has done differently to win in second trial. Since Alice and Bob, both are playing to win the game and both are equally clever then “Alice has to think about Bob’s move means options available for the Bob once Alice is done with the move, What Bob will pick (Bob is equally clever and tries to leave Alice with minimum values to be chosen from) and then what Alice will chose.”

So if we can clearly see that each player is making the move by keeping in mind the two moves can be made in future and pick the best of them.

Let’s make it more clear- Suppose we have coins lined up from Ci to Cj wit the values of Vi to Vj respectively.

MV(i, j) = maximum value the Alice can collect from i'th coin to j'th coin.
In every move Alice has 2 options –

Either pick the ith coin (from starting)
OR pick the jth coin ( from the end).
Let’s discuss both the options

Alice Picks the ith coin (from starting)

As we can see above if Alice picks the ith coin, Ci then Bob will be left with 2 choices Ci+1 and Cj, since Bob is equally clever than Bob will pick the coin which will leave the Alice with minimum value coins.

So if Bob picks i+1th coin then it will again Alice turn and problem will be reduced to Alice has to pick a coin from i+2th to jth coin and similarly if if Bob picks jth coin then it will again Alice turn and problem will be reduced to Alice has to pick a coin from i+1th to j-1th coin.

So Alice will collection will be

= Vi + Min{MV(i+2,j), MV(i+1, j-1)}

Alice Picks the jth coin (from the end)

As we can see above if Alice picks the jth coin, Cj then Bob will be left with 2 choices Ci and Cj-1, since Bob is equally clever than Bob will pick the coin which will leave the Alice with minimum value coins.

So if Bob picks ith coin then it will again Alice turn and problem will be reduced to Alice has to pick a coin from i+1th to j-1th coin and similarly if Bob picks j-1th coin then it will again Alice turn and problem will be reduced to Alice has to pick a coin from ith to j-2th coin.

So Alice will collection will be

= Vj + Min{MV(i+1,j-1), MV(i, j-2)}
So now we need to decide whether Alice should pick ith coin or jth coin. Alice will pick the coin which ever gives the more value considering 2 moves ahead

so

MV(i, j) = Max { Vi + Min{MV(i+2,j), MV(i+1, j-1)} , Vj + Min{MV(i+1,j-1), MV(i, j-2)}}

Description of Change

References

Checklist

Added description of change
Added file name matches File name guidelines
Added tests and example, test must pass
Relevant documentation/comments is changed or added
PR title follows semantic commit guidelines
Search previous suggestions before making a new one, as yours may be a duplicate.
I acknowledge that all my contributions will be made under the project's license.

Notes:

_{🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.}

## 📋 Pull Request Information **Original PR:** https://github.com/TheAlgorithms/C/pull/632 **Author:** [@Bhavykapadiya](https://github.com/Bhavykapadiya) **Created:** 10/1/2020 **Status:** ❌ Closed **Base:** `master` ← **Head:** `patch-1` --- ### 📝 Commits (1) - [`0f266df`](https://github.com/TheAlgorithms/C/commit/0f266df6a41d4c870f64d58ed16754e9aad859ee) Create Dynamic programming Algorithm ### 📊 Changes **1 file changed** (+39 additions, -0 deletions) <details> <summary>View changed files</summary> ➕ `Dynamic programming Algorithm` (+39 -0) </details> ### 📄 Description Objective: In this game, which we will call the coins-in-a-line game, an even number, n, of coins, of various denominations from various countries, are placed in a line. Two players, who we will call Alice and Bob, take turns removing one of the coins from either end of the remaining line of coins. That is, when it is a player’s turn, he or she removes the coin at the left or right end of the line of coins and adds that coin to his or her collection. The player who removes a set of coins with larger total value than the other player wins, where we assume that both Alice and Bob know the value of each coin. Example: coins [] = { 6, 9, 1, 2, 16, 8} trial 1: (players will pick the best option available for them) coins [] = { 6, 9, 1, 2, 16, 8} , Alice picks 8 coins [] = { 6, 9, 1, 2, 16}, Bob picks 16 coins [] = { 6, 9, 1, 2}, Alice picks 6 coins [] = { 9, 1, 2}, Bob picks 9 coins [] = {1, 2}, Alice picks 2 coins [] = {1}, Bob picks 1 Alice: 8+6+2 =16 Bob: 16+9+1=26 => Alice Lost So clearly picking up the best in each move is not good for Alice. What else Alice can do to win the game. trial 2: (Alice thinks about Bob's move, Will discuss the strategy in solution) coins [] = { 6, 9, 1, 2, 16, 8} , Alice picks 6 coins [] = { 9, 1, 2, 16, 8}, Bob picks 9 coins [] = { 1, 2, 16, 8}, Alice picks 1 coins [] = 2, 16, 8}, Bob picks 8 coins [] = {2, 16}, Alice picks 16 coins [] = {2}, Bob picks 2 Alice: 6+1+16 =23 Bob: 9+8+2=19 => Alice Won So this time Alice has won. Let's see the solution and discuss what Alice has done to win the game. Approach: We will solve this problem using Dynamic programming in Bottom-up manner. In the example above we have seen that in trail 1 Alice has lost and in trial 2 Alice has won. So clearly picking the best coin available in each move is good option for Alice. So the question is what Alice has done differently to win in second trial. Since Alice and Bob, both are playing to win the game and both are equally clever then “Alice has to think about Bob’s move means options available for the Bob once Alice is done with the move, What Bob will pick (Bob is equally clever and tries to leave Alice with minimum values to be chosen from) and then what Alice will chose.” So if we can clearly see that each player is making the move by keeping in mind the two moves can be made in future and pick the best of them. Let’s make it more clear- Suppose we have coins lined up from Ci to Cj wit the values of Vi to Vj respectively. MV(i, j) = maximum value the Alice can collect from i'th coin to j'th coin. In every move Alice has 2 options – Either pick the ith coin (from starting) OR pick the jth coin ( from the end). Let’s discuss both the options Alice Picks the ith coin (from starting) As we can see above if Alice picks the ith coin, Ci then Bob will be left with 2 choices Ci+1 and Cj, since Bob is equally clever than Bob will pick the coin which will leave the Alice with minimum value coins. So if Bob picks i+1th coin then it will again Alice turn and problem will be reduced to Alice has to pick a coin from i+2th to jth coin and similarly if if Bob picks jth coin then it will again Alice turn and problem will be reduced to Alice has to pick a coin from i+1th to j-1th coin. So Alice will collection will be = Vi + Min{MV(i+2,j), MV(i+1, j-1)} Alice Picks the jth coin (from the end) As we can see above if Alice picks the jth coin, Cj then Bob will be left with 2 choices Ci and Cj-1, since Bob is equally clever than Bob will pick the coin which will leave the Alice with minimum value coins. So if Bob picks ith coin then it will again Alice turn and problem will be reduced to Alice has to pick a coin from i+1th to j-1th coin and similarly if Bob picks j-1th coin then it will again Alice turn and problem will be reduced to Alice has to pick a coin from ith to j-2th coin. So Alice will collection will be = Vj + Min{MV(i+1,j-1), MV(i, j-2)} So now we need to decide whether Alice should pick ith coin or jth coin. Alice will pick the coin which ever gives the more value considering 2 moves ahead so MV(i, j) = Max { Vi + Min{MV(i+2,j), MV(i+1, j-1)} , Vj + Min{MV(i+1,j-1), MV(i, j-2)}} #### Description of Change  #### References  #### Checklist  - [ ] Added description of change - [ ] Added file name matches [File name guidelines](https://github.com/TheAlgorithms/C/blob/master/CONTRIBUTING.md#File-Name-guidelines) - [ ] Added tests and example, test must pass - [ ] Relevant documentation/comments is changed or added - [ ] PR title follows semantic [commit guidelines](https://github.com/TheAlgorithms/C/blob/master/CONTRIBUTING.md#Commit-Guidelines) - [ ] Search previous suggestions before making a new one, as yours may be a duplicate. - [ ] I acknowledge that all my contributions will be made under the project's license. Notes:  <a href="https://gitpod.io/#https://github.com/TheAlgorithms/C/pull/632"><img src="https://gitpod.io/api/apps/github/pbs/github.com/Bhavykapadiya/C.git/0f266df6a41d4c870f64d58ed16754e9aad859ee.svg" /></a> --- <sub>🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.</sub>

claunia added the pull-request label 2026-01-29 15:17:29 +00:00

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: starred/C#1086