动态规划系列之四梅花桩问题

如果你不相信努力和时光,那么成果就会是第一个选择辜负你的。不要去否定你自己的过去,也不要用你的过去牵扯你现在的努力和对未来的展望。不是因为拥有希望你才去努力,而是去努力了,你才有可能看到希望的光芒。动态规划系列之四梅花桩问题,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

动态规划系列之四梅花桩问题

题目

Redraiment是走梅花桩的高手。Redraiment总是起点不限,从前到后,往高的桩子走,但走的步数最多,不知道为什么?你能替Redraiment研究他最多走的步数吗?
例如梅花桩的高度:

2 5 1 5 4 5

结果分析:
6个点的高度各为 2 5 1 5 4 5
如从第1格开始走,最多为3步, 2 4 5
从第2格开始走,最多只有1步,5
而从第3格开始走最多有3步,1 4 5
从第5格开始走最多有2步,4 5

所以这个结果是3

梅花桩问题是最长升序数组问题。

动态规划解题思路

使用动态规划解题,需要题目符合动态规划的解决思路。动态规划解题思路是:

  1. 将大的问题拆解成小一点问题,小问题和大问题的解决思路是类似的
  2. 小问题之间的关系能完成大问题的最优解

通常拆解问题的方法有两种,一种是二分法,把数组拆成两个。第二种是将将数组逐个递减,拆解成多个小数组。对于本体来说,第二种方式比较适合。

小规模问题和大规模问题之间有某种联系,这种联系就是动态转移方程。通过小规模问题的解决,能够解决大规模问题,直到解决最终的问题。
题目是要求数组 [2,5,1,5,4,5]中最长的升序数组。可以按照动态规划的思路,将大问题拆解成小问题。求6个元素的最长升序,可以拆解成求5个,同理求5个元素的,可以拆解成求4个。最后一直到1个。

[2,5,1,5,4,5]
[2,5,1,5,4]
[2,5,1,5]
[2,5,1]
[2,5]  
[2]  

各个小问题之间有一定联系,通过找到小问题之间的联系,求出最优解。小问题之间的联系就是状态转移方程。

建立数学模型

求最多的步数,但不知道是从哪一步开始算最多。所以就创建一个数组dp,数组dp中存储从第一个梅花桩到当前梅花桩的步数。因为求的步数,最少也走一步,所以dp的初始值就是

dp = [1,1,1,1,...1]

状态转移方程

当前梅花桩最多的步数,就是拿当前梅花桩逐个和前面的梅花桩比较,当前梅花桩高就比较是比当前小的梅花桩的最大值+1大 还是 该梅花桩本身的值大。通俗来说就是找出梅花桩数值小的。即:

dp[j] + 1 大 还是 dp[i] 大

下标为0时,dp数组

2 5 1 5 4 5
1 1 1 1 1 1

下标为1时,dp数组。
因为 5 比 2大,所有,dp[0] + 1 > dp[1],所以dp[1]=1+1=2

2 5 1 5 4 5
1 2 1 1 1 1

下标为2时,dp数组:
1 < 5, 1< 2,所以dp数组不变,dp[2] = 1

2 5 1 5 4 5
1 2 1 1 1 1

下标为3时,dp数组:
5 > 1,所以dp[3] = max(dp[2]+1,dp[3]) = max(2,1) = 2
同时,5 > 2 ,所以dp[3] = max(2,dp[0]+1) = max(2,2) = 2。
所以dp[3] = 2

2 5 1 5 4 5
1 2 1 2 1 1

下标为4时,dp数组:
4 > 1 ,dp[4] = max(dp[4],dp[2]+1) = max(1,2) = 2

2 5 1 5 4 5
1 2 1 2 2 1

下标为5时,dp数组:
5 > 4 ,dp[5] = max(dp[5],dp[4]+1) = max(1,3) = 3
5 > 1 ,dp[5] = max(3,1) = 3
5 > 2 ,dp[5] = max(3,1) = 3

2 5 1 5 4 5
1 2 1 2 2 3

边界值

边界值很清晰就是第一个梅花桩就一步,也就是dp[1,x,x,x,x,x]

代码实现

def GetResult(l):
    n=len(l) # 传入list的长度
    dp=[1]*n # dp[i]表示以第i个桩为结尾,最多走多少步,初始是1步
    
    for i in range(n):# i表示第几个桩
        for j in range(i):# j表示i前面的桩
            if l[i]>l[j]: #当第j个桩小于第i个桩的值时,第j个桩有dp[j]个上升的序列。
                dp[i]=max(dp[i],dp[j]+1)#这时比较dp[j]+1和dp[i]大。因为可能会存在比dp[j]更大的序列,所以要找出最大的。
    
    #dp代表下标为i时上升序列。max找出其中最大的即为所求
    return max(dp)
 
if __name__ == "__main__":

    l=[2,5,1,5,4,5]
    ans=GetResult(l)
    print(ans)

小结

梅花桩问题的的巧妙之处在于构建了一个dp数组,该数组中存储了到下标i最长升序个数。然后比较arr[i]和arr前面的所有元素的值,如果arr[i]大于前面的元素的值,那么也就是说arr[i]是升序的数组的下一个元素。但如果arr[i]大于很多个前面的元素的话,就要选择一个最大的值,所以循环比较i和之前的元素,取一个最大值。

数组类动态规划解法

最大和子数组最长升序数组 这两个问题能代表着数组类动态规划的求解方式,两个问题的相似之处为:
a. 都将问题转化成以求解第i个元素为结尾的问题
b. 构建dp数组,填充以第i个元素为结尾的最优解
c. 都将大规模问题拆解成小规模问题
d. 小规模问题小到极限有一个边界值,最大和的边界为只有一个元素时就是自身,最长升序的边界为只有一个元素时升序值为1

这四个规律也是求解数组类动态规划问题的四个步骤

同时两个问题也有不同之处:
a. 最大和子数组,dp数组中代表着以i为结尾的数组的最大值,下一个值只和上一个值有关,保证连续性
b. 最长升序数组,dp数组中代表这以i为结尾的升序数组的个数。下一个值与前面所有的值都有关联,要拿到前面值中的最大值。因为其不需要保证连续性,所有需要遍历前面的dp。最大和子数组只需要比较前一个。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/194250.html

(0)
小半的头像小半

相关推荐

半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!