算法篇——动态规划

核心思想：

将问题分解为重叠的子问题，并储存子问题的解（使用字典、数组或哈希表），避免重复计算，从而提高效率。

题目特点：重叠子问题（特殊地，是最优子结构）

比如：斐波那契数列问题中，递归求F(5)，需要多次计算F(3)；

最短路径问题中，若从A到C的最优路径包含B，则A到B和B到C也必然是最优的。

两种实现方式：

自顶向下（递归+储存记忆，将大问题逐步分解，子问题的解储存在字典里）：

class Solution(object):# 把momory作为类属性memory = {}def fib(self, n):# 如果已经在记忆里储存，则直接返回，不用再重复计算if n in self.memory: return self.memory[n]if n<=1:return nself.memory[n] = self.fib(n-1)+self.fib(n-2)return self.memory[n]

自底向上（迭代+储存记忆，先解决小问题再解决大问题，小问题的解储存在数组里）：

class Solution(object):def fib(self, n):""":type n: int:rtype: int"""dp = [0,1] # 动态规划数组，初始值相当于递归里遇到终止条件能直接返回的值for i in range(2,n+1):dp.append(dp[i-1]+dp[i-2])return dp[n]

解题步骤：

1、定义状态（dp[i]表示什么）

2、写状态转移方程（由局部最优一直推到全局最优，所以从初始截断到当前位置来考虑即可，后面的先不管）

3、确定初始状态（起码两个）

3、用递归or迭代解题

比如：“打家劫舍”求数组中不相邻元素组合，使值的和最大

（1）定义状态：设dp[i]表示从第0到第i个中元素组合的最优解；

（2）状态转移方程：

则可以分类讨论：目前最优解要不要加上dp[i]这个元素，

即是取dp[i-1]还是dp[i-2]+nums[i]，

比较两者取较大值就行。

得方程，dp[i] = max（dp[i-1]，dp[i-2]+nums[i]）

（3）初始条件：dp[0]=1，dp[1]=max（nums[0]，nums[1]）

class Solution(object):def rob(self, nums):""":type nums: List[int]:rtype: int"""n = len(nums)if n==1:return nums[0]dp = [nums[0],max(nums[0],nums[1])] #注意基础条件里，nums[1]不一定有，需要分类讨论for i in range(2,n):dp.append(max(dp[i-1],dp[i-2]+nums[i]))return dp[n-1]

删除并获得点数

class Solution(object):def deleteAndEarn(self, nums):""":type nums: List[int]:rtype: int"""# 转换思维：统计每个数字的总点数，生成一个数组sums[x] = x*count(x)# 接着，类似于打家劫舍问题，取不相邻的元素，使元素的和最大# 设dp[i]为遍历到i的最优解，dp[i] = max(dp[i-1],dp[i-2]+sums[i])# 生成sums数组（先找到nums[i]的最大值，用它作为sums数组的最大边界）max_num = max(nums)sums = [0] * (max_num+1) #初始化for num in nums:sums[num] += num# 动态规划求解if len(sums) == 1:return 0dp = [0,sums[1]]#dp = [sums[0],max(sums[0],sums[1])]for i in range(2,len(sums)):dp.append(max(dp[i-1],dp[i-2]+sums[i]))return dp[len(sums)-1]

优化技巧：

1、滚动变量替代dp数组

class Solution(object):def rob(self, nums):n = len(nums)if n==1:return nums[0]# 滚动变量优化空间，不需要整个dp数组pre, cur = nums[0],max(nums[0],nums[1]) #dp = [nums[0],max(nums[0],nums[1])]for i in range(2,n):pre, cur = cur, max(cur, pre+nums[i])#dp.append(max(dp[i-1],dp[i-2]+nums[i]))return cur

可以理解为先计算temp = max(cur, pre + nums[i])，然后让pre=cur，再让cur=temp。

最长回文子串：

（1）定义状态：dp[i][j]表示字符串从第i个字符到第j个字符是否为回文字符串。

（2）状态转移方程：

往子问题方向拆分——如果dp[i][j]是回文子串，那么两端的字符必定相等，而且中间的字符串（如果有）也应该是回文子串。即

dp[i][j] = （s[i]==s[j]）&&（（j==i+1）or dp[i+1][j-1]）

（3）初始条件：

只有一个字符，dp[i][i]=True

则，可以总结出：dp[i][i]=True

dp[i][j] = （s[i]==s[j]）&& （（j==i+1）or dp[i+1][j-1]）

迭代法的状态转移：判断首尾相等后，每个位置的状态和它的左下角的状态有关

class Solution(object):def longestPalindrome(self, s):""":type s: str:rtype: str"""n = len(s)if n<=1:return s# 初始化动态规划表dp = [[False]*n for _ in range(n)]# 初始条件：所有长度为1的子串都是回文for i in range(n):dp[i][i] = Truemax_len = 1start = 0 #追踪最长回文子串的起始位置# dp[i][j] = （s[i]==s[j]）&& （（j==i+1）|| dp[i+1][j-1] ）for j in range(1,n): #右指针，子区间的右边界，从1到n-1for i in range(0,j): #左指针，子区间的左边界，从0到j-1if s[i]==s[j]: #如果左右边界相等if (j==i+1) or (dp[i+1][j-1]): #如果没有中间部分或者中间部分也是回文子串dp[i][j] = True #标记length = j-i+1if length>max_len: #看需不需要更新max_len=lengthstart=i return s[start:start+max_len]

[False] * n 借助列表乘法操作，将包含单个 False 的列表重复 n 次，从而生成一个长度为 n 且所有元素都为 False 的一维列表。

_ 是 Python 里的一个惯用变量名，通常用于表示一个临时的、不会被使用的变量。

s[start:start+max_len] 是 Python 中用于字符串切片操作（左闭右开）的表达式。它的作用是从字符串 s 中提取一个子字符串，该子字符串从索引 start 开始，到索引 start + max_len - 1 结束。