动态规划问题

力扣44、72 、70

Posted by songjiu on March 15, 2019

动态规划问题

核心思想:自底向上,相比递归来说可以利用一些过程中的结果,减少一些重复计算。具体实现则是构建dp表,如以下来自网络的小例子:

A * "1+1+1+1+1+1+1+1 =?" *

A : "上面等式的值是多少"
B : *计算* "8!"

A *在上面等式的左边写上 "1+" *
A : "此时等式的值为多少"
B : *quickly* "9!"
A : "你怎么这么快就知道答案了"
A : "只要在8的基础上加1就行了"
A : "所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"
--------------------- 
作者:HankingHu 
来源:CSDN 
原文:https://blog.csdn.net/u013309870/article/details/75193592 
版权声明:本文为博主原创文章,转载请附上博文链接!

相关题目及代码

力扣44

https://leetcode-cn.com/problems/wildcard-matching/

def isMatch(self, s: str, p: str) -> bool:
        ls=len(s)
        lp=len(p)
        #首先制作动态规划表
        dp=[[False for i in range(lp+1)]for j in range(ls+1)] 

        #如果s.p都空,那么dp表只有True了,返回True
        dp[0][0]=True 
        #首先填写第一行,当p为星号时,即当p的子串最后一个为星时,记为True
        for i in range(1,lp+1):
            if p[i-1]=='*':
        #为什么要用i-1,j-1呢,因为我们填表是填(传递)答案,判断字符要判断答案之前的两个子序列    
                dp[0][i]=dp[0][i-1]
        #开始正是填写,首先从s取一位,开始判断dp表,答案是第二排
        for i in range(1,ls+1):
                    for j in range(1,lp+1):
                        if p[j-1]=='*':
                            dp[i][j]=dp[i][j-1] or dp[i-1][j]
                        else:
                            dp[i][j]=(s[i-1]==p[j-1] or p[j-1]=='?') and dp[i-1][j-1]

        return dp[ls][lp]

力扣72 https://leetcode-cn.com/problems/edit-distance/

    def minDistance(self, word1: str, word2: str) -> int:
        m=len(word1)
        n=len(word2)
        dp=[[0 for _ in range(n+1)]for _ in range(m+1)]
        for j in range(m+1):
            dp[j][0]=j
        for j in range(n+1):
            dp[0][j]=j
        print(dp)
        for i in range(1,m+1):
            for j in range(1,n+1):
                if word1[i-1]==word2[j-1]:
                    dp[i][j]=dp[i-1][j-1]
                else:
                    dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1
        print(dp)
        return dp[m][n]

力扣70 https://leetcode-cn.com/problems/climbing-stairs/

 def climbStairs(self, n: int) -> int:
        '''
        Solution.result=0
        self.dfs(n,0)
        return self.result
        '''
        condition = [0] * (n + 1)
        condition[0] = 1
        condition[1] = 1
        for i in range(2, n+1):
            condition[i] = condition[i-1] + condition[i-2]#因为一次只能走1或2步,所以第i步的方法由i-1步和i-2步提供。
        return condition[n]