由于本人算法基础比较薄弱，所以在这里把做过的题整理一下，方便随时随地复习。那么，本文会继续更新一些我遇到的比较经典的动态规划题目。如果您对代码有任何疑问，请在文章下方评论。我会尽快回复。一、我对动态规划的理解网上已经有很多介绍动态规划的文章，所以在这里我还是想谈谈我的理解，希望能给大家带来一些启发。我理解的动态规划就两个字：dynamic和planning。我对动力学的理解是：一个问题可以拆分成若干个子问题，然后通过逐步递归得到最终的结果。规划是一个最优问题，整体最优又细分为各个递归环节的最优。那么，要解决动态规划问题，最重要的就是找到状态转移方程。我理解的状态转移方程是指：一个通用方程，即任何中间状态都可以从前一个状态推导出来。比如下图中的dp[i][j]状态，可以从左上角的三个状态推导出来。对于很多动态规划问题，大部分的具体解都是用一个二维数组来存储中间环节的最优解。最后，找到二维数组中的最大值或最后一个值。另一种情况是：如果当前状态只与前一个状态有关，那么可以将二维数组优化为一维数组，这样空间复杂度就从O(n2)优化到O(n)。2.示例排列2.1经典01背包问题题目描述：一个人去偷东西，他的背包最大容量为20kg，然后有不同重量和价值的物品，比如重量为2的物品和a价值3。对于每件物品只能取一件，求小偷能偷到的物品的最大价值。"""物品重量与数值对应关系：wv233458910背包容量：20"""importnumpyasnpdeffunc(pack,cap):max_value_arr=np.zeros([len(pack)+1,cap+1])#第一列第一行全为0，这样max_value_arr后面的值就可以递归了max_value_arr[:,0]=0max_value_arr[0,:]=0#i表示packitemfor的序号iinrange(1,len(pack)+1):#j表示pack中剩余空间forjinrange(1,cap+1):#第一种情况，pack中剩余空间不足如果j0，那么本项末尾的最大子序列和就是前一项加上自身defmaxSubArray(nums):l=len(nums)res=[0foriinrange(l)]foriinrange(l):ifi==0：res[??i]=nums[i]否则：如果res[i-1]<=0：res[??i]=nums[i]否则：res[??i]=nums[i]+res[i-1]returnmax(res)2.5最长的升序子序列（Leetcode300）题目描述：给定一个无序的整数数组，找出最长的升序子序列的长度。例子：输入：[10,9,2,5,3,7,101,18]输出：4解释：最长的上升子序列是[2,3,7,101]，它的长度是4#最长上升子序列（动态规划)#res[i]表示以此项结尾的最大上升子序列的长度#关键是比较当前值nums[i]和之前的值nums[j]#如果比它大，那么就可以将1加到res[j]。最后遍历完nums的前j个元素后，加上最大值为res[i]deflengthOfLIS(nums):l=len(nums)ifl==0:return0res=[1foriinrange(l)]foriinrange(l):max_=1temp=0forjinrange(i):ifnums[i]>nums[j]:temp=res[j]+1iftemp>max_:max_=tempres[i]=max_returnresnums=[10,9,2,5,3,7,101,1]print(lengthOfLIS(nums))#2,3,7,101maxis42.6swingsequence(Leetcode376)题目描述：如果连续数字之间的差严格在正负之间交替，则一个数字序列称为振荡序列。第一个差异（如果有的话）可能是正数或负数。少于两个元素的序列也是摆动序列。给定一个整数序列，返回作为摆动序列的最长子序列的长度。子序列是通过从原始序列中删除一些（或不删除）元素而获得的，其余元素保持其原始顺序。例如：输入：[1,17,5,10,13,15,10,5,16,8]输出：7解释：这个序列包含几个长度为7的摆动序列，其中一个可以是[1,17,10,13,10,16,8]。#这道题分为，如果上一次摆动是正摆动，那么这次如果是负摆动，最长摆动序列就是最长摆动序列加1，#如果这次是正摆动或者没有摆动，则最长摆动sequence是最后一个最长的摆动序号；如果上一次摆动是负数，那么#如果这次是正摆动，则最长摆动序列是上一次最长摆动序列加1，如果这次是负摆动或没有摆动，则最长摆动序列是最长摆动上次的序号。用一个数组记录上一次最长的摆动序列，以备后用。test_list=[1,17,3,20,15,6,7,8]defswing(test):如果len(test)<2:returnlen(test)up=1down=1idx=1n=len(测试)whileidxtest[idx-1]:up=down+1iftest[idx]
