python动态规划及编辑距离计算实例

动态规划的三要素:最优子结构,边界和状态转移函数,最优子结构是指每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到(子问题的最优解能够决定这个问题的最优解),边界指的是问题最小子集的解(初始范围),状态转移函数是指从一个阶段向另一个阶段过度的具体形式,描述的是两个相邻子问题之间的关系(递推式)

成都创新互联专业提供成都主机托管四川主机托管成都服务器托管四川服务器托管，支持按月付款！我们的承诺：贵族品质、平民价格，机房位于中国电信/网通/移动机房，成都机柜租用服务有保障！

重叠子问题,对每个子问题只计算一次,然后将其计算的结果保存到一个表格中,每一次需要上一个子问题解时,进行调用,只要o(1)时间复杂度,准确的说,动态规划是利用空间去换取时间的算法.

判断是否可以利用动态规划求解,第一个是判断是否存在重叠子问题。

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2

输出： 2

解释： 有两种方法可以爬到楼顶。

1.  1 阶 + 1 阶

2.  2 阶

示例 2：

输入： 3

输出： 3

解释： 有三种方法可以爬到楼顶。

1.  1 阶 + 1 阶 + 1 阶

2.  1 阶 + 2 阶

3.  2 阶 + 1 阶

分析:

假定n=10,首先考虑最后一步的情况,要么从第九级台阶再走一级到第十级,要么从第八级台阶走两级到第十级,因而,要想到达第十级台阶,最后一步一定是从第八级或者第九级台阶开始.也就是说已知从地面到第八级台阶一共有X种走法,从地面到第九级台阶一共有Y种走法,那么从地面到第十级台阶一共有X+Y种走法.

即F(10)=F(9)+F(8)

分析到这里,动态规划的三要素出来了.

边界:F(1)=1,F(2)=2

最优子结构:F(10)的最优子结构即F(9)和F(8)

状态转移函数:F(n)=F(n-1)+F(n-2)

class Solution(object):

def climbStairs(self, n):

    """

    :type n: int

    :rtype: int

    """

    if n=2:

        return n

    a=1#边界

    b=2#边界

    temp=0

    for i in range(3,n+1):

        temp=a+b#状态转移

        a=b#最优子结构

        b=temp#最优子结构

    return temp

利用动态规划的思想计算编辑距离。

编辑距离是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。通常来说，编辑距离越小，两个文本的相似性越大。这里的编辑操作主要包括三种：

插入：将一个字符插入某个字符串；

删除：将字符串中的某个字符删除；

替换：将字符串中的某个字符替换为另外一个字符。

那么，如何用Python计算编辑距离呢？我们可以从较为简单的情况进行分析。

当两个字符串都为空串，那么编辑距离为0；

当其中一个字符串为空串时，那么编辑距离为另一个非空字符串的长度；

当两个字符串均为非空时(长度分别为 i 和 j )，取以下三种情况最小值即可：

1、长度分别为 i-1 和 j 的字符串的编辑距离已知，那么加1即可；

2、长度分别为 i 和 j-1 的字符串的编辑距离已知，那么加1即可；

3、长度分别为 i-1 和 j-1 的字符串的编辑距离已知，此时考虑两种情况，若第i个字符和第j个字符不同，那么加1即可；如果相同，那么不需要加1。

很明显，上述算法的思想即为 动态规划 。

求长度为m和n的字符串的编辑距离，首先定义函数——edit(i, j)，它表示第一个长度为i的字符串与第二个长度为j的字符串之间的编辑距离。动态规划表达式可以写为：

if i == 0 且 j == 0，edit(i, j) = 0

if （i == 0 且 j 0 ）或者 （i 0 且j == 0），edit(i, j) = i + j

if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + d(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，d(i, j) = 1；否则，d(i, j) = 0。

def edit_distance(word1, word2):

len1 = len(word1)

len2 = len(word2)

dp = np.zeros((len1 + 1,len2 + 1))

for i in range(len1 + 1):

    dp[i][0] = i   

for j in range(len2 + 1):

    dp[0][j] = j

for i in range(1, len1 + 1):

    for j in range(1, len2 + 1):

        delta = 0 if word1[i-1] == word2[j-1] else 1

        dp[i][j] = min(dp[i - 1][j - 1] + delta, min(dp[i-1][j] + 1, dp[i][j - 1] + 1))

return dp[len1][len2]

edit_distance('牛奶','华西奶')

结果：2

Python怎么根据不同的字符串动态选择函数？

#可以用函数字典，看看是否满足你的要求

def text_func(self):

print "this is text func"

def int_func(self):

print "this is int_func"

gen_func={'text':text_func, 'int':int_func}

def choose(a='text'):

return gen_func[a]

Python高难度代码例子、Python最复杂代码例子

#IT教育# #IT# #程序员# #人工智能#

最近学习pytorch，看到下面的Python高难度代码例子和Python最复杂代码例子：

from google.colab import output as colab_output

from base64 import b64decode

from io import BytesIO

from pydub import AudioSegment

RECORD = """

const sleep = time = new Promise(resolve = setTimeout(resolve, time))

const b2text = blob = new Promise(resolve = {

const reader = new FileReader()

reader.onloadend = e = resolve(e.srcElement.result)

reader.readAsDataURL(blob)

})

var record = time = new Promise(async resolve = {

stream = await navigator.mediaDevices.getUserMedia({ audio: true })

recorder = new MediaRecorder(stream)

chunks = []

recorder.ondataavailable = e = chunks.push(e.data)

recorder.start()

await sleep(time)

recorder.onstop = async ()={

blob = new Blob(chunks)

text = await b2text(blob)

resolve(text)

}

recorder.stop()

})

"""

def record(seconds=1):

display(ipd.Javascript(RECORD))

print(f"Recording started for {seconds} seconds.")

s = colab_output.eval_js("record(%d)" % (seconds * 1000))

print("Recording ended.")

b = b64decode(s.split(",")[1])

fileformat = "wav"

filename = f"_audio.{fileformat}"

AudioSegment.from_file(BytesIO(b)).export(filename, format=fileformat)

return torchaudio.load(filename)

waveform, sample_rate = record()

print(f"Predicted: {predict(waveform)}.")

ipd.Audio(waveform.numpy(), rate=sample_rate)

js 的Promise函数对象编程，字符串javascript函数对象，IPython解释js对象，解释结果和python代码结合，IPython Shell显示非字符串数据，python音频使用IPython简单调用。

复杂Python模块下的多知识点结合代码，是Python高难度代码的体现。

Js的Promise理解为动态函数，比C++的类成员函数和全局函数这类静态形式的函数处理灵活，不过初学者理解起来麻烦。代码里sleep和b2text都代表一些处理函数，也就是几行代码，而不是数据。通常来讲，变量一般代表数据，但是这里代表了指令。

python的类中怎么实现动态化函数？

给你这样一个例子吧，这个例子里面有动态增加类的函数。

声明一个类，类初始化的时候读取配置文件，根据配置列表加载特定目录下的模块下的函数，函数和模块同名，将此函数动态加载为类的成员函数。

代码如下所示：

class WinBAS(Bas):

def __init__(self):

self.__baslist = {}

self.__Init_Modules()

pass

def __Init_Modules(self):

import modplugs

for m in modplugs.__moduleset__:

mh = __import__('modules.' + m)# + '.' + m)

ma = getattr(mh, m)# + '.' + m)

ma = getattr(ma, m)

setattr(self.__class__, m, ma)

modplugs.py是模块配置文件如下：

__moduleset__ = [

'BAS_GetUserList',

]

然后建立目录modules下面建立一个空的__init__.py文件，把目录变为一个包，在modules目录下建立真正的BAS_GetUserList实现：BAS_GetUserList文件中有个BAS_GetUserList函数如下：

def BAS_GetUserList(self, strs):

return [0, strs]

这样WinBAS类就可以动态加入了BAS_GetUserList函数。

网页题目：python动态函数 python动态函数图像设计
文章网址：http://scyanting.com/article/hihpoj.html