算法之动态规划问题
发布日期:2021-08-26 13:56:21 浏览次数:1 分类:技术文章

本文共 3116 字,大约阅读时间需要 10 分钟。

态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推的方式去解决。

动态规划的核心点:定义状态与转移方程(最优子结构)

重新定义问题:

一、最长上升子序列(LIS):给定一个序列X,求X长度最大的连续递增的子序列。

例:X=[1,7,2,8,3,5,2],LIS(X)=[1,2,3,5]

def LIS(x):    F = [0 for _ in range(len(x))]    p = [-1 for _ in range(len(x))]    # 初始化    F[0] = 1    p[0] = -1    for k in range(1, len(F)):        max_loc = -1        max_num = 0        # 内层循环表示F[0:k]里所有小于x[k]的对应位置的F[i]的最大值        for i in range(0, k):            if x[i] < x[k]:                if F[i] > max_num:                    max_loc = i                    max_num = F[i]        F[k] = max_num + 1        p[k] = max_loc    max_i = 0    for i in range(1,len(F)):        if F[i] > F[max_i]:            max_i = i    lis = []    i = max_i    while i >= 0:        lis.append(x[i])        i = p[i]    lis.reverse()    return lis# print(LIS([9,7,2,8,3,5,2]))

 二、最长公共子序列(LCS)问题:给定两个序列X和Y,求X和Y长度最大的公共子序列。

例:X="ABBCBDE" Y="DBBCDB" LCS(X,Y)="BBCD"

动态规划最优子结构:

def LCS(x, y):    F = [[0 for _ in range(len(y)+1)] for _ in range(len(x)+1)]    p = [[0 for _ in range(len(y)+1)] for _ in range(len(x)+1)]    for i in range(1, len(x)+1):        p[i][0] = 2    for j in range(1, len(y)+1):        p[0][j] = 1    # 0 斜向  1 横向 j-1   2竖向 i-1    for i in range(1, len(x)+1):        for j in range(1, len(y)+1):            if x[i-1] == y[j-1]:                F[i][j] = F[i-1][j-1]+1                p[i][j] = 0            else:                #F[i][j] = max(F[i-1][j], F[i][j-1])                if F[i-1][j] > F[i][j-1]:                    F[i][j] = F[i-1][j]                    p[i][j] = 2                else:                    F[i][j] = F[i][j-1]                    p[i][j] = 1    lcs = []    i = len(x)    j = len(y)    while i > 0 or j > 0:        if p[i][j] == 0:            lcs.append(x[i-1])            i -= 1            j -= 1        elif p[i][j] == 1:            j -= 1        else:            i -= 1    lcs.reverse()    return lcs    #return F[i][j]# print(LCS("ABBCBDE", "DBBCDB"))

 

三、最长公共子序列(LCSS)问题:给定两个序列X和Y,求X和Y长度最大的公共子串。

例:X="ABBCBDE" Y="DBBCDB" LCSS(X,Y)="BBC"

暴力搜索求解:O(n3)

动态规划最优子结构:

def LCSS(x, y):    F = [[0 for _ in range(len(y)+1)] for _ in range(len(x)+1)]    p = [[0 for _ in range(len(y)+1)] for _ in range(len(x)+1)]    # 0 不匹配 1匹配    for i in range(1, len(x)+1):        for j in range(1, len(y)+1):            if x[i-1] == y[j-1]:                F[i][j] = F[i-1][j-1]+1                p[i][j] = 1            else:                F[i][j] = 0                p[i][j] = 0    max_val = 0    max_i = 0    max_j = 0    for i in range(1, len(x)+1):        for j in range(1, len(y)+1):            if F[i][j] > max_val:                max_val = F[i][j]                max_i = i                max_j = j    #tracback    lcss = []    i = max_i    j = max_j    while p[i][j] == 1:        lcss.append(x[i-1])        i -= 1        j -= 1    lcss.reverse()    return lcssprint(LCSS("ABBCBDE", "DBBCDB"))

 

四、编辑距离:指两个字串之间,由一个转成另一个所需的最少编辑操作次数。

允许的编辑操作:替换、插入、删除x="cofe" y="coffee",编辑距离为2(插入2次)

  • x="coffee" y="coffe",编辑距离为(删除1次)
  • x="coffee" y="coffye",编辑距离为(替换2次)
  • x="cofye" y="coffee",编辑距离为2

编辑距离可以用来表示两个字符串的相似度,应用广泛

动态规划最优子结构:

斜着过来是替换

从左边来的是插入

从上面来的是删除

代码待续。。。。。。。。。。

 

转载地址:https://blog.csdn.net/weixin_33888907/article/details/85969260 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:wget命令的几个常用选项和示例
下一篇:(九)unity4.6学习Ugui中文文档-------參考-UGUI Rect Transform

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月16日 15时31分52秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

win iis对比apache php,服务器Apache与IIS的区别 2019-04-21
怎样用xampp测试php环境变量,使用xampp配置php运行环境的方法 2019-04-21
qq互联php教程,thinkphp5怎么整合qq互联登录教程 2019-04-21
editor.md使用php,editor.md 配置参数和使用方法 2019-04-21
python mod,mod_python的安装 2019-04-21
python分析彩票数据,这波太炸了!Python脚本可视化居然可以这么玩 2019-04-21
简单的mysql重置root密码,重置mysql的root密码最简单的方法 2019-04-21
用matlab仿真mmc环流抑制器,一种基于准PR控制原理的MMC阀组环流抑制方法 2019-04-21
oracle 排序的分析函数,Oracle SQL:使用分析排序函数 2019-04-21
oracle direct for hdfs xi下载,ORACLE连接HDFS有个专项的解决方案 2019-04-21
java 403怎么抛出_java – 如何在Spring MVC中返回403禁止? 2019-04-21
java jsch工具类_Java工具集-JSch连接远程服务器工具类 2019-04-21
cmd背景变红1003无标题_怎样修改cmd中文字的大小、颜色和背景颜色呢 原来是这样的... 2019-04-21
php rand() 重复,php – mt_rand()给我总是相同的数字 2019-04-21
php taglib.php,thinkphp5 taglib自定义标签教程 2019-04-21
java常用包类 array,Java中的StringBuffer和数组Arrays以及常用类型的包装类 2019-04-21
ctf常见php,CTF中常见的PHP伪协议 2019-04-21
php语言冒泡法,PHP 冒泡排序法 2019-04-21
php如何数组去重复,PHP如何去除数组重复元素? 2019-04-21
java转换ab的值,查看新闻/公告--[整理]Java将AB1234形式的16进制字符串转换为10进制数值,考虑字节序的影响.... 2019-04-21