探讨“ 两头取数的问题” 的程序设计思路

lulijie

我觉得是O(2^n)的算法。
确定第一步有2个取法，再确定第二步也是2种取法，一共要18步，所以是2^18-1种方法。

zxl0714

看来你还没有理解啊。。。。。
动态规划的主要思想就是避免重复计算，你可以这么想，为了确定第1步我们要计算出所有的来比较，第2步我们就不用再计算了，因为第1步已经计算过了。

lulijie

有道理，我要好好想想。
你试过没有，要费多少时间？我要尽量向你的目标靠拢。

zxl0714

我贴个伪码

1. input n
   
2. sum( 0 ) := 0
   
3. for i := 1 to n
   
4. begin
   
5.         input a( i )
   
6.         f( i, i ) := a( i )
   
7.         sum( i ) := sum( i - 1 ) + a( i )
   
8. end
   
9. for i := 1 to n
   
10.         for j := 1 to n
    
11.                 f( j, i + j ) = sum( i + j ) - sum( j - 1 ) - min( f( j + 1, i + j ), f( j, i + j - 1 ) )
    
12. print f( 1, n ), sum( n ) - f( 1, n )        //f( 1, n )是S甲，sum( n ) - f( 1, n )是S乙
    
13. 
    
14. //下面开始输出每个数第几次被取走
    
15. start := 1
    
16. end := n
    
17. for i := 1 to n
    
18. begin
    
19.         if f( start + 1, end ) < f( start, end - 1 )
    
20.         begin
    
21.                 p( start ) := i
    
22.                 start := start + 1
    
23.         end
    
24.         else
    
25.         begin
    
26.                 p( end ) := i
    
27.                 end := end - 1
    
28.         end
    
29. end
    
30. for i := 1 to n
    
31.         print p( i )

复制代码

zxl0714

对于那个样例是0.000s，对于1000个数是0.031s，大部分时间是耗在了打印那1000个数是第几个被取走。

yang_bigarm

原帖由 zxl0714 于 2009-4-4 22:01 发表
看来你还没有理解啊。。。。。
动态规划的主要思想就是避免重复计算，你可以这么想，为了确定第1步我们要计算出所有的来比较，第2步我们就不用再计算了，因为第1步已经计算过了。

all, right! 正解！

其实不管是用递归还是动态规划，这个问题都可以求解，这两种方法求解问题各有千秋。
相比之下，递归的思路容易理解，但是动态规划的效率要跟高些(但动态规划并不总是能将指数量级的复杂度变成多项式级别的)，我们把它称作循环式；
但是如果在递归的时候记录中间过程的话，递归式也不会输给循环式(这个时候已经不是严格的递归了)。

现代计算机程序设计里面的一个非常核心的问题就是如何把递归式变成循环式，美国麻省理工学院的教科书《计算机程序的构造和解释》对这方面做了比较详尽的讲解，但是太难了，我也没有耐心把它看完。

zxl0714

递归其实就是一个栈，完全可以自己用栈来模拟递归，这样就把递归变成循环了。但是这样会比较麻烦，所以我一般都是写递归，但是递归的最大缺陷就是有可能会造成栈溢出，而且时间效率比循环稍低。
我一般把记录中间过程的递归叫做“记忆化搜索”，如果不带记忆其实就是一个dfs搜索算法。

lulijie

我知道它的精髓了。重新设计一下，运行结果如下：
先手方赚：189
取数顺序：18 17 16 15 1 14 2 13 12 11 10 9 8 7 6 5 4
花费时间：0秒

lulijie

哈哈，3600个数组成的数列，2秒解出最优取法。
先手方赚：27934
取数顺序：1 2 3600 3599 3598 3597 3596 3595 3594 3593 3592 3591 3590 3589 3588 3587 3586 3585 3584 3583 3582 3581 3580 3579 3578 3577 3576 3575 3574 3573 3572 3571 3570 3569 3568 3567 3566 3565 3564 3563 3562 3561 3560 3559 3558
......... ......
106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4
花费时间：1.99999983888119秒

lulijie

跟高手们确实学到很多，受益匪浅啊!