Pots of gold game: 누가 돈을 많이 받는지

문제 설명:
Pots of gold game: Two players A & B. There are pots of gold arranged in a line, each containing some gold coins (the players can see how many coins are there in each gold pot - perfect information). They get alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player which has a higher number of coins at the end. The objective is to "maximize"the number of coins collected by A, assuming B also plays optimally. A starts the game. The idea is to find an optimal strategy that makes A win knowing that B is playing optimally as well. How would you do that?
 
간단하게 말하면 많은 금화통이 한 줄로 늘어서서 두 사람이 번갈아 돈을 받는다.매번 실 끝에 있는 깡통만 가져가도 두 가지 선택이 있다.A부터 시작해서 A가 어떤 전략으로 가능한 한 많은 돈을 받아야 하는지 물어볼게요.B도 똑똑하고 매번'최고'결정이다
 
답변:
매우 교묘해서 동적 계획이 여기에 사용되었다.
매번 A는 두 가지 선택이 있기 때문에 머리나 꼬리 부분의 금화 탱크를 선택한다.우리는 머리를 선택한다고 가정해도 무방하다. 그러면 이때 B가 선택할 차례가 된다. B도 두 가지 선택이 있는데 이때의 "머리"또는 "꼬리"를 선택한다.문제는 하위 문제의 최적화를 포함하고 있다는 것을 알아차렸다. 이 특성이 비교적 뚜렷하면 설명을 많이 하지 않을 것이다. 이렇게 이해할 수 있다.'영명'결정은 하나하나의'영명'결정으로 구성된다.
그래서 우리는 동적 기획의 방식으로 해결할 수 있다

   1:  function max_coin( int *coin, int start, int end ):

   2:      if start > end:

   3:          return 0

   4:      

   5:      int a = coin[start] + 

max

( max_coin( coin, start+2,end ), max_coin( coin, start+1,end-1 ) )

   6:      int b = coin[end] + 

max

( max_coin( coin, start+1,end-1 ), max_coin( coin, start,end-2 ) )

   7:      

   8:      return max(a,b)

<!--
.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }
-->
여러분 이 코드를 보고 문제가 있는지 자세히 연구해 보세요.
 
다섯 번째 문장을 잠그고 자연어로 해석해 봅시다.A선저금통을 선택한 후 B의 선택에 따라 두 가지 상황이 있는데 두 가지 상황에서 가장 좋은 결과를 얻는다.최우선
여기까지 분석하면 여러분은 문제의 출현을 느꼈습니까?없으면 다시 한번 봅시다.
A 최우해 선택!이게 무슨 뜻이야, 그러니까 B의 선택이 A에 영향을 미치지 않는다는 거야!B의 선택이 무엇이든 A의 선택은 일정하기 때문이다.
이것은 분명히 불합리하다!
그래서 정확한 코드는

   1:  function max_coin( int *coin, int start, int end ):

   2:      if start > end:

   3:          return 0

   4:      

   5:      int a = coin[start] + min( max_coin( coin, start+2,end ), max_coin( coin, start+1,end-1 ) )

   6:      int b = coin[end] + min( max_coin( coin, start+1,end-1 ), max_coin( coin, start,end-2 ) )

   7:      

   8:      return max(a,b)

 
 
<!--
.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }
-->
이 코드를 보면 이상하게 느껴질 수도 있어요. 민으로 바꿔도 B가 A의 선택에 영향을 미쳤다는 뜻은 아닌 것 같아서요.그런 것 같지만, 그렇죠?
 
사실대로 말하면, 나는 엄밀하게 증명할 수 없다.
잠시 이렇게 이해합시다. B는 전략을 취했습니다. 그것은 곳곳에서 A를 난처하게 하는 것입니다. 매번 선택은 하나의 원칙을 따랐습니다. 그것은 바로 다음 A가 얻은 총 화폐 수를 가능한 한 적게 하는 것입니다.A가 가능한 한 적으면 B도 자연히 가능한 한 많아진다.
 
QUORA에 이런 코드가 있어요. 봐도 돼요. 괜찮아요.
http://www.quora.com/Dynamic-Programming/How-do-you-solve-the-pots-of-gold-game

 1 pots = [...]

 2 

 3 cache = {}

 4 def optimal(left, right, player):

 5     if left > right:

 6         return 0

 7     if (left, right, player) in cache:

 8         return cache[(left, right, player)]

 9     if player == 'A':

10         result = max(optimal(left + 1, right, 'B') + pots[left],

11                      optimal(left, right - 1, 'B') + pots[right])

12     else:

13         result = min(optimal(left + 1, right, 'A'),

14                      optimal(left, right - 1, 'A'))

15     cache[(left, right, player)] = result

16     return result

17 

18 answer = optimal(0, len(pots)-1, 'A')