【学习笔记】LeetCode练习-动态规划【学习笔记】LeetCode练习-动态

LeetCode练习-动态规划

主要思想
练习题

主要思想
动态规划是求解决策过程最优化的过程，往往用于优化递归问题，以减少计算量。一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。
练习题
300.最长上升子序列
题目：给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:

输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

【【学习笔记】LeetCode练习-动态规划】代码：

def lengthOfLIS(nums): if not nums:return 0 dp=[1]*len(nums) for i in range(len(nums)): for j in range(i): if nums[i]>nums[j]: dp[i]=max(dp[i],dp[j]+1) return max(dp) print(lengthOfLIS([10,9,2,5,3,7,101,18]))

5. 最长回文子串
题目：给定一个字符串 s，找到 s 中最长的回文子串。可假设 s 的最大长度为 1000。

示例：输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。

代码：

def longestPalindrome(s): length=len(s) if length<2:#判断边界条件 return s dp=[[False for _ in range(length)]for _ in range(length)] #定义dp状态矩阵 max_len=1 start=0 #后续记录回文串初试位置 for j in range(1,length): for i in range(j): #矩阵中逐个遍历 if s[i]==s[j]: if j-i<3: dp[i][j]=True else: dp[i][j]=dp[i+1][j-1] if dp[i][j]: #记录位置，返回有效答案 cur_len=j-i+1 if cur_len>max_len: max_len=cur_len start=i return s[start:start+max_len] print(longestPalindrome("babad"))

(TBD)