动态规划刷题

红太狼 2023-07-18 06:58 12阅读 0赞

# 分金子（360公司2017春招真题） #

### 题目链接 ###

https://exercise.acmcoder.com/online/online\_judge\_ques?ques\_id=3863&konwledgeId=42  
可以去链接里看一看，不再赘述题目了。

### 解题思路 ###

假设几个变量，f(i,j)是从\[i，j\]中可以拿到的最大价值，因为只可以从两端拿，假如先手是从最左端拿的，那剩下的最大价值就是f(i+1,j)，也就是后手能拿到的最大价值；那先手能拿到的最大价值可以用sum(i,j)-f(i+1,j)来表示。  
假如先手是从最右端拿的，剩下最大价值就是f(i,j-1)，也就是后手能拿到的最大价值；那先手能拿到的最大价值可以用sum(i,j)-f(i,j-1)来表示。  
那究竟应该从哪边拿，当然是看f(i+1,j)和f(i,j-1)的大小，最后可以提炼出

f(i,j) = max{(sum(i,j)-f(i+1,j)),sum(i,j)-f(i,j-1)} = sum(i,j)-min{f(i+1,j),f(i,j-1)}

### 代码实现 ###

#### 递归版 ####

从上式可以看出，递归是一种解决方案，为了避免重复计算，使用一个变量来记录算出来的f(n,m)的值。

def digui(lst,i,j):
        if(i==j):
            return lst[i]
        elif(res[i][j]!=0):
            return res[i][j]
        else:
            res[i][j]=sum(lst[i:j+1])-min(digui(lst,i+1,j),digui(lst,i,j-1))
            return res[i][j]
    
    n=int(input())
    for q in range(n):
        num=int(input())
        res = [[0]*(num+1) for i in range(num+1)]
        lst=list(map(int,input().split()))
        lst=[0]+lst
        a=digui(lst,1,num)
        b=sum(lst)-digui(lst,1,num)
        print("Case #%s: %s %s"%(q+1,a,b))

#### 动态规划版 ####

我也说不上来什么叫做动态规划，总之大家都是这样叫的，当初看别人代码时，也是一脸懵比，然后自己整个手推了一遍，豁然开朗。  
我们使用给的案例

4 7 2 9 5 2

上面是一列金子，先画一张表，为了方便表示，我们从1开始，0列0行都当作是空白

接下来可以填表了，假如是从\[1,1\]取，那就一种取法，就是该位置上的数量，其他只有一个金子的情形也是这样，填表。

那如果是\[1,2\]该怎么取呢，公式交给我们，应该是先得到\[1,2\]的和，然后减去较小的那个，那\[2,3\],\[3,4\]也是类似。

规律很明显了，接着填表即可，最后表的状态如下。

那\[1,6\]最大的收益就是1行6列的18了，后面只需要交给计算机来帮我们填表即可。

n=int(input())
    for q in range(n):
        num=int(input())
        lst = list(map(int,input().split()))
        res = [[0]*(num+1) for i in range(num+1)]
        for i in range(1,num+1):
            res[i][i] = lst[i-1]
        cnt=1
        while cnt<=num:
            i=1
            j=i+cnt
            while j<=num:
                res[i][j] = sum(lst[i-1:j]) - min(res[i][j-1],res[i+1][j])
                i+=1
                j+=1
            cnt+=1
        a = res[1][num]
        b = sum(lst) - a
        print("Case #%s: %s %s"%(q+1,a,b))

欢迎关注公众号，一起进步

![公众号二维码.jpg][.jpg]

[.jpg]: /images/20230528/4245df545a5a4f0a89dcf613030d9f36.png