首页 > 其他分享 >day44-dynamic programming-part11-8.15

day44-dynamic programming-part11-8.15

时间:2024-08-15 12:57:31浏览次数:10  
标签:programming len text2 range nums2 8.15 day44 nums1 dp

tasks for today:

1. 1143.最长公共子序列

2. 1035.不相交的线

3. 53.最大子序和

4. 392.判断子序列 (编辑距离问题)

------------------------------------------------------------------------------

1. 1143.最长公共子序列

300: single, ascending, non-continuity

674: single, ascending, continuity

718: double, continuity

1143: double, non-continuity

in this practice, the key difference from 718 is that, 718 requires contuinuity while this practice does not require contunuity.

The logic "else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])" is added in code snippet.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if (len(text1) == 1 and text1[0] not in text2) or (len(text2) == 1 and text2[0] not in text1): return 0
        if (len(text1) == 1 and text1[0] in text2) or (len(text2) == 1 and text2[0] in text1): return 1

        dp = [[0] * (len(text2)+1) for _ in range(len(text1)+1)]
        result = 0
        
        for i in range(1, len(text1)+1):
            if text1[i-1] == text2[0]:
                dp[i][1] = 1
        
        for j in range(1, len(text2)+1):
            if text1[0] == text2[j-1]:
                dp[1][j] = 1

        for i in range(1, len(text1)+1):
            for j in range(1, len(text2)+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                    
                if dp[i][j] > result:
                    result = dp[i][j]
        
        return result

2. 1035.不相交的线

This practice is the same with practice 1143, the essence and the code is the same, which both aims to find the sub list having the same sequence and not necesarily continuous.

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        if (len(nums1) == 1 and nums1[0] in nums2) or (len(nums2) == 1 and nums2[0] in nums1): return 1
        if (len(nums1) == 1 and nums1[0] not in nums2) or (len(nums2) == 1 and nums2[0] not in nums1): return 0
 
        dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
        result = 0
 
        for i in range(1, len(nums1)+1):
            if nums1[i-1] == nums2[0]:
                dp[i][1] = 1
        
        for j in range(1, len(nums2)+1):
            if nums1[0] == nums2[j-1]:
                dp[1][j] = 1
 
        for i in range(1, len(nums1)+1):
            for j in range(1, len(nums2)+1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
 
                if dp[i][j] > result:
                    result = dp[i][j]
 
        return result

3. 53.最大子序和

This practice should be compared with practice 674, both of which do not require continuity. The recursive equation aims to compare the bigger one between nums[i] and dp[i-1] + nums[i].

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1: return nums[0]
        dp = [0] * len(nums)
        dp[0] = nums[0]
        result = nums[0]

        for i in range(1, len(nums)): 
            dp[i] = max(nums[i], dp[i-1] + nums[i])
            if dp[i] > result:
                result = dp[i]
        
        return result

4. 392.判断子序列

This practice also involve two sequence, so this necessitates a dp table with 2-dim.

This practice is similar to practice 1143, the key difference, the length relationship between s and t. In this practice, the s is no longer than t, so the "dp[i][j] = max(dp[i-1][j], dp[i][j-1])" can be simpified to "dp[i][j] = dp[i][j-1]" when s[i-1] != t[j-1].

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if len(s) == 0: return True
        if len(s) > len(t) or (len(s) == len(t) and s != t): return False

        dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]

        for i in range(1, len(s)+1):
            if t[0] in s[:i]:
                dp[i][1] = 1

        for j in range(1, len(t)+1):
            if s[0] in t[:j]:
                dp[1][j] = 1

        for i in range(1, len(s)+1):
            for j in range(1, len(t)+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    # method1: this expression can be same with practice 1143
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                    # method2: while also can be optimized, because in this practice, s should be no longer than the t, so this express can be simplified to following equation
                    dp[i][j] = dp[i][j-1]
        
        if dp[-1][-1] == len(s): return True
        else: return False

标签:programming,len,text2,range,nums2,8.15,day44,nums1,dp
From: https://blog.csdn.net/bbrruunnoo/article/details/141214202

相关文章

  • 面向对象编程(OOP: Object Oriented Programming ):类、对象、构造方法、封装
    目录一、类1、定义(1)属性(2)方法2、类的定义方法二、对象1、定义2、对象的定义方法三、类和对象的关系1、现实世界都是由很多对象组成的,基于对象的共同特征抽象出类。2、对象:真实存在的对象3、类是对象的模板,对象是类的具体实例。4、一个类可以创建多个对象,同一个......
  • Object-Oriented Programming
    Object-OrientedProgrammingResitCourseworkThisassignmentinvolvesthedevelopmentofJavaclassesandaprogramtosupportanalysisofearthquakedatacompiledbytheUnitedStatesGeologicalSurvey.Wehaveprovidedthreeexampledatasetsthatyou......
  • The 2022 ICPC Asia Taoyuan Regional Programming Contest
    Preface由于今天HDU多校是自己学校出的题,因此像我这种没出题的就可以白兰一天爽歪歪然后和祁神找了场Ucup来VP,这场傻逼题巨多,不那么傻逼的题后面发现被搬到去年暑假前集训了,然后直接3h10题下班后期徐神全力冲刺他最喜欢的造计算机题,反观某人已经在Celeste启动了,怎么......
  • 2020 China Collegiate Programming Contest, Weihai Site
    Preface难得没有发疯的一场,但只能说是症状减轻了,感觉离痊愈还有一定距离这场基本就跟着榜慢慢开题,中期下机的时候才发现J我把题意读假了然后让队友推了快3h的假结论,还好最后把J过了不然铁战犯A.GoldenSpirit签到分讨题,但也需要一些细心大致思路就是在\(2nt\)那个......
  • COSC2391 Further Programming
    COSC2391 FurtherProgramming/COSC1295AdvancedProgrammingAssignment 1–Semester2 2024IntroductionYouarerequiredtoimplementabasicJavaprogram usingJava.This assignment is designed to:•   TestyourknowledgeofbasicJava concepts......
  • Lab0 C Programming Lab(CMU)(CSAPP深入理解计算机系统)
    该文章是我在别处写的小随笔,现在转过来实验下载地址15-213/14-513/15-513:IntrotoComputerSystems,Spring2022大致要求1.Linux命令行基础2.C语言基础3.数据结构基础(链表基本操作)4.基本英语阅读能力大致操作下载.tar文件,解压后对着README操作即可;简单来说,允许直......
  • Python - Functional programming
    Functionalprogrammingisaprogrammingparadigminwhichmostoftheworkinaprogramisdoneusingpurefunctions.Apurefunctionisafunctionwithoutanysideeffects;itsreturnvalueisalwaysdeterminedbyitsinputarguments,soitalwaysreturn......
  • 《Programming from the Ground Up》阅读笔记:p88-p94
    《ProgrammingfromtheGroundUp》学习第5天,p88-p94总结,总计7页。一、技术总结1.touppercase.s#PURPOSE:Thisprogramconvertsaninputfile#toanoutputfilewithallletters#convertedtouppercase.#PROCESSING:#(1)Opentheinputfile#(2)Opentheoutput......
  • 动态规划(Dynamic programming)
    什么是动态规划?动态规划(英语:Dynamicprogramming,简称DP),是一种在数学、管理科学、计算机科学经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。以上定义来自维基百科,看定义感觉还......
  • COMP1921 Programming Module
    SchoolofComputing:AssessmentbriefModuletitleProgrammingProjectModulecodeCOMP1921AssignmenttitleResitAssessmentAssignmenttypeanddescriptionYouwillproducecodetomeetagivenspecification.RationaleThisassessmentgivesyoua......