从斐波那契数列和零一背包问题探索动态规划

看过vivo和阿里巴巴的校招算法题，可以清楚的知道绝对有动态规划。如果不是，那出题的面试官就真的不行了。动态规划摔倒N次后，润森最近一直在动态规划上下功夫。这篇文章浪费了三天。阅读Leetcode公众号的文章：https://mp.weixin.qq.com/s/rhyUb7d8IL8UW1IosoE34g极客时间朝哥的动态规划，拉勾教育的算法专栏。润森真的不想在DP里，死一次又一次。死了N次，学了N次，就是他妈写不出来。动态规划需要解决三个系列：三个背包、零钱问题和库存问题。今天润森开始杀最重要的“背包问题”。三背包问题：01背包、多背包、满背包。动态规划前置知识动态规划的“状态转移方程”一词：比如润森一般看到的状态转移方程：dp[n]=dp[n-1]+dp[n-2]。》最优子结构：一般从最优子结构推导出一个状态转移方程f(n)，问题的递归实现方法可以很快写出来。把一个大问题变成几个小问题，在几个小问题中找到问题的最佳解决方案。”》重叠子问题：比如斐波那契数列中的f(5)，在计算了f(4)和f(3)之后，结果f(4)又对润森计算了f(3)。其实就是就是修剪一棵二叉树，方法就是将备忘录存入内存。”《自下而上：逆向求解》动态规划思想动态规划是一种寻找问题最优解的方法。大体思路：将问题的解转化为==>求解子问题，==>递归，==>最小的子问题是可以直接得到的初始状态。详细步骤如下：判断是否可以使用递归求解，如果可以，转步骤2分析递归过程中是否存在大量重复的子问题。用memo保存子问题的解，避免大量重复计算（切分支）自下而上递归，即动态规划的关键是“求状态转移方程”。斐波那契数列和爬楼梯问题斐波那契数列最早是从兔子问题演化而来的。假设一对新生兔在一个月内成熟，一对成熟兔每月产一对兔，一年内没有死亡。.那么，一对刚出生的兔子一年后可以繁殖出多少对兔子呢？我们直接看下面的图1,1,2,3,5,8,13,21,34,55,89,144,233...上面的规律是发现每月兔子对数=上月兔对数+本月新生兔数=上月兔对数+上月兔对数得到序列：1,1,2,3,5、8、13、21、34、55、89、144、233……这个数列就是斐波那契数列“（Fibonaccisequence）”。斐波那契数列中的任何数字都称为斐波那契数。斐波那契数列通常用于解释递归函数。尝试用递归的思想来解决，但是时间复杂度高。deffib(n):ifn<=1:return1returnfib(n-1)+fib(n-2)foriinrange(20):print(fib(i),end='')然而，我们发现时间复杂度为highas主要原因是存在重复计算。例如，fib(3)将计算fib(2)+fib(1)，而fib(2)将计算fib(1)+fib(0)。这个fib(1)是一个完全重复的计算。不应该为它再次递归调用，而应该在第一次解决后“记住”。这就是备忘录方案，用空间换时间的思路。将已经获得的解放放在字典Map或者list列表中，下次直接拿，不用重复结算。备忘录解的代码和动态规划的代码和思路基本一致。斐波那契数列在Leetcode中有一道类似的题，就是Leetcode第70题，爬楼梯，每次可以爬1、2步。你有多少种不同的方式可以爬到建筑物的顶部？注：给定n为正整数。输入：2输出：2解释：有两种方式可以爬到楼顶。1.1阶+1阶2.2阶斐波那契数列和爬楼梯问题的状态转移方程为：dp[i]=dp[i-1]+dp[i-2]。但是dp需要初始化，否则会报listassignmentindexoutofrange的错误。下面是斐波那契数列爬楼梯题的解答代码，也是Leetcode70题的解答代码。classSolution:defFibonacci(self,n):ifn==0:return1ifn==1:return1ifn>1:dp=[0]*(n+1)dp[0]=1dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]Leetcode53最大子序列和最大子序列和，润森记得很清楚，是Leetcode的53题。输入：[-2,1,-3,4,-1,2,1,-5,4]，输出：6解释：连续子数组[4,-1,2,1]的和最大，这是6。声明两个变量，currentSum：前一个连续值的和，maxSum：当前最大的子序列和。最大子序列和状态转移方程f(i)=max(f(i),f(i)+nums[i+1])defmaxSubArray(nums):'''求连续子数组的最大和args:nums:IntegerarrayReturns:返回整数数组的最大子序列和'''#比较当前子序列和，最大子序列和，返回最大值#定义当前子序列和和最大子序列和为首元素cursum=maxsum=nums[0]foriinrange(1,len(nums)):cursum=max(nums[i],cursum+nums[i])print(cursum)#将当前值与定义的最大子序列和值进行比较，最大重新赋值给max_summaxsum=max(cursum,maxsum)print(maxsum)returnmaxsumprint(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))前面只是动态规划为了热身，润森首先进入“强化系列三背包问题”，01背包问题是动态规划的入门阶段。01背包问题对应题目：https://www.acwing.com/problem/content/2/01背包问题是只有一件物品。输入格式：第一行包含两个整数N和V，中间用空格隔开，分别代表物品的数量和背包的体积。接下来有N行，每行有两个整数vi，wi，中间用空格隔开，分别代表第i个物品的体积和价值。输出格式：输出一个表示最大值的整数。数据范围：0=goods[i-1][0]:#是否选择最大值的情况下dp[i][j]=max(dp[i-1][j],dp[i-1][j-goods[i-1][0]]+goods[i-1][1])else:#第i项未选中dp[i][j]=dp[i-1][j]print(dp)print(dp[-1][-1])#测试数据5101223344556[[1,2],[2,3],[3,4],[4,5],[5,6]][[0,0,0,0,0,0,0,0,0,0,0],[0,2,2,2,2,2,2,2,2,2,2],[0,2,3,5,5,5,5,5,5,5,5],[0,2,3,5,6,7,9,9,9,9,9],[0,2,3,5,6,7,9,10,11,12,14],[0,2,3,5,6,7,9,10,11,12,14]]14#2+3+4+5上面的代码，如果你知道dp和statetransitionEquation是怎么定义的，那跟Runsen写的一样快。其实那时候润森的文笔还挺慢的，也许你比润森好。上面的代码是通过状态定义的二维数组，有些大佬甚至可以通过状态定义一维数组，节省空间。“润森想不通。”只能说润森真的好。我要努力去弥补！一维数组去掉了状态，遍历方式改为“倒序”遍历到c[i]。因此润森可以优化解空间，将二维数组压缩成一维数组。这时候转移方程就变成了：'''@作者：Runsen@微信：RunsenLiu@微信公众号：Python之王@CSDN：https://blog.csdn.net/weixin_44510615@Github：https://github.com/MaoliRUNsen@Date:2020/9/10'''n,v=map(int,input().split())goods=[]foriinrange(n):goods.append([int(i)foriininput().split()])print(goods)#[[1,2],[2,3],[3,4],[4,5],[5,6]]dp=[0foriinrange(v+1)]foriinrange(n):#因为要放置物品，从空间v遍历到0forjinrange(v,-1,-1):#判断背包的容量是否大于i的体积-thitemifj>=goods[i][0]:#更新j的状态，即当前容量放入item后的状态dp[j]=max(dp[j],dp[j-goods[i][0]]+goods[i][1])print(dp)print(dp[-1])5101223344556[[1,2],[2,3],[3,4],上面的[4,5],[5,6]][0,2,3,5,6,7,9,10,11,12,14]14是01背包最后的解法，由于有限文章数和多个背包，完整的背包会写在下一篇博文！！！不知不觉到现在已经写了几天了，代码反反复复的写。写完博客，真的好累！谁说我的算法比较弱！希望以后能遇到01背包的问题，??也就是在恐怖的算法面试中遇到了润森的爱情！参考[1]传送门~：https://github.com/MaoliRUNsen/runsenlearnpy100