数据结构和算法12,最长考拉兹序列 [复制链接]

动态规划即DynamicProgramming，简称DP，无论是在日常生活还是在工程问题中都有着十分广泛的应用，比如最短路径问题，购物满减问题等等。动态规划也是算法中较难的一个模块，而其中最大的问题在于如何确定状态以及状态转移方程，“状态”这一词在后面说明。本文将从递归开始一步一步讲解到动态规划。

动态规划是一种将复杂问题拆分成相对简单的子问题并自下而上求解每个子问题最优解从而求解初始问题最优解的模型。以下是维基百科对DynamicProgramming的定义：

DynamicProgrammingisamethodforsolvinga
　　输入：n=2
　　输出：1示例2：
　　输入：n=5
　　输出：5\

走1:能递归吗？肯定可以呀，上图\

classSolution{publicintfib(intn){if(n2)returnn;returnfib(n-1)+fib(n-2);}}

走2:递归过程有重复子问题嘛，当然，继续上图走3:有的话，直接来个备忘录记录子问题\

\

classSolution{MapInteger,Integermap=newHashMap();publicintfib(intn){if(map.containsKey(n)){returnmap.get(n);}if(n2){if(!map.containsKey(n)){map.put(n,n);}returnn;}intm=fib(n-1)%+fib(n-2)%;if(!map.containsKey(n)){map.put(n,m%);}returnm%;}}

走4:走四，就放到定三里一并讲解。

首先，自顶而下肯定有重复子问题＝定１其次，状态量即为F(N)，状态转移方程为F(N)=F(N-1)+F(N-2),其中N1＝定２最后，初始值0,1＝定３那么动态规划就是0
　　
　　　1
　　
　　　1g
　　
　　　fg
　　
　　
　　
　　
　　f=f+gg
　　
　　
　　
　　
　　f
　　
　　　g=f-g
　　f
　　
　　　g
　　
　　　f如上进行移动，仅需两个变量即可完成.

classSolution{publicintnumWays(intn){if(n==0)return1;intf=1,g=0;for(inti=1;i=n;i++){f=f%+g;g=f-g;}returnf%;}}打家劫舍

今天入门到小进阶：一种最为简单的打家劫舍，具体题目在力扣上有三个难度，自行查看。

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。示例1：
　　输入：[1,2,3,1]
　　输出：4解释：偷窃1号房屋(金额=1)，然后偷窃3号房屋(金额=3)。
　　　偷窃到的最高金额=1+3=4。示例2：
　　输入：[2,7,9,3,1]
　　输出：12解释：偷窃1号房屋(金额=2),偷窃3号房屋(金额=9)，接着偷窃5号房屋(金额=1)。
　　　偷窃到的最高金额=2+9+1=12。\

其实打家劫舍就是一个取舍的问题，当前房子偷还是不偷的问题

偷的金币最大值

走1:递归可以做吗？当然可以，根据问题分析，我们只需比较当前房屋偷和不偷所得的金额谁更大选择谁即可，那么迭代也按照条件，当前偷了则跳过相邻房屋，否则继续从相邻房屋进行访问。\

classSolution{publicintrob(int[]nums){if(nums.length==0)return0;returnmyrob(nums,0);}publicintmyrob(int[]nums,intcur){if(cur=nums.length)return0;intsteal=nums[cur];steal+=myrob(nums,cur+2);intnotSteal=0;notSteal+=myrob(nums,cur+1);intmax=Math.max(steal,notSteal);returnmax;}}

走2:有大量重复子问题吗？当然有，比如第三个房屋如果偷，那么跳到第五个房间进行计算，然而当第四个房间不偷，同样也会跳到第五个房间进行计算。走3:备忘录带上，查小本本啦！\

classSolution{MapInteger,Integermap=newHashMap();publicintrob(int[]nums){if(nums.length==0)return0;returnmyrob(nums,0);}publicintmyrob(int[]nums,intcur){if(cur=nums.length)return0;if(map.containsKey(cur))returnmap.get(cur);intsteal=nums[cur];steal+=myrob(nums,cur+2);intnotSteal=0;notSteal+=myrob(nums,cur+1);intmax=Math.max(steal,notSteal);map.put(cur,max);returnmax;}}

走4:动态规划，当然可以，放到定三一起分析。

定三：当然此处我是做了空间优化，所以只使用了三个变量首先，确定了肯定有重复子问题的出现＝定1其次，状态量确定dp0代表着前一房屋不偷到该房屋后所得金额，dp1代表着前一房屋偷了到该房屋不偷所得金额，dp则取其中最大值最为求解结果，若此时处于第i屋，那么根据问题分析则dp=max{dp0+nums,dp1}＝定2最后，最底层初始值三者皆为0＝定3\

classSolution{publicintrob(int[]nums){intdp0=0,dp1=0,dp=0;for(inti=0;inums.length;i++){dp=Math.max(dp1,dp0+nums);dp0=dp1;dp1=dp;}returndp1;}}总结

动态规划初步讲解就到这里结束了，其实内容不是很多，主要在于练习。谨记走四定三就可以解决大部分DP问题，总结下来即为以下几个问题：