java算法day27

java算法day27

• 动态规划初步总结
• 509 斐波那契数
• 198 打家劫舍
• 70 爬楼梯

动态规划初步总结

如果你感觉某个问题有很多重叠子问题，使用动态规划是最有效的。
动态规划的过程就是每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心了。贪心是“直接”从局部选最优的。

看到目前的各种教程，目前能看懂的动态规划思想总结就是：
这三步：
1、穷举法（暴力搜索）
2、记忆化搜索（剪枝）
3、改写成迭代形式。

目前我只能一步步的做题来体会动态规划。

509 斐波那契数列

目前就拿着上面总结的思想来做做题。

拿到这个题，我上来就想到了递归解法（这也对应着上面的第一点）。然后快速就交了，过了，但是超越百分之5。足以见得效率非常的低。

class Solution {public int fib(int n) {if(n == 0){return 0;}if(n == 1){return 1;}return fib(n-2) + fib(n-1);}
}

问题出在哪里，从递归树里就清楚了

从这个计算过程可以看到，存在着大量的重复计算。比如计算f(18)和f(19)的时候，都会计算f(17)，而计算f(17)的过程又需要往下递归，意思说f(17)要算两次。往下那肯定存在更多的重复性计算。所以说这是需要优化的点。

如何优化，如何实现快速访问，这里我们可以想到哈希，下次我要计算之前，我先不着急递归，我先去hash里面看看有没有现成的，直接哪来用。那么按照这样的想法我们就可以创建一个哈希表，至于这个表是什么样的，可以根据题目来。

有时候可能还想不通，那这个hash里面的值是怎么记录下来的，那我只能说要把递归的过程想清楚。
通过上面的代码，算f(5) return f(4) + f(3) 。那么按程序执行顺序来说，肯定是先进f(4)，然后一直往下走
比如f(4) return f(3) + f(2)
f(3) = f(2) + f(1)
然后f(2) = f(1)+f(0) 。可以见得，在不断下去的过程中，f(4),f(3),f(2),f(1),f(0)都会计算。所以说在这最左边的分支，其实就已经把别的分支那些重复的点全计算完了。所以hash就是在这里就完成了计算，怎么算？这个过程中程序要进行计算，hash表直接把这个结果也存到自己的哈希表里不就完事了。

从这个过程，再对上面的递归树做一个优化，你可以看到这样的变化。

是不是感觉2^n级别的复杂度立马变o(n)了。

带备忘录的写法如下：

class Solution {public int fib(int n) {if(n<1){return 0;}int[] memo = new int[31];return helper(n,memo);}int helper(int n,int[] memo){if(n == 1 || n == 2){return 1;}if(memo[n]!=0){return memo[n];}memo[n] = helper(n-1,memo)+helper(n-2,memo);return memo[n];}}

这么这就是dp了吗？还不是！
这其实还是一个自顶向下的解法。

真正的dp是什么。真正的dp是自底向上，从最小的子问题开始，然后逐步构造最大的解，直到达到目标。

动态规划的本质：动态规划的核心是通过解决子问题来解决更大的问题，在斐波那契数的例子中，我们直到每个数都是前两个数的和。

所以这里可以总结出动态规划问题的真正含义了。
我先来说说动态规划是如何解决这个问题的，首先如果清楚子问题是什么样的，然后清楚子问题的初状态，那么我就能够直接从这个子问题出发，不断地进行状态运算，直到状态转移到最终结果。然后这个得到下一个状态的方法，就是所谓的状态转移方程。

所以这里可以总结一个结论：
也就是很多教程里面教的方法：
子问题的识别：
正如你所说，清楚地识别子问题是关键。在斐波那契数列中，子问题就是计算每个 F(i)。

初始状态（基本情况）：
这些是已知的最小子问题的解。在斐波那契数列中，F(0) = 0 和 F(1) = 1。

状态转移：
这是从一个子问题到另一个子问题的过程。在斐波那契数列中，状态转移方程是 F(i) = F(i-1) + F(i-2)。

最终状态：
这是我们最终要求解的问题。在斐波那契数列中，就是计算 F(n)。

从初始状态到最终状态：
正如你所说，我们可以从初始状态开始，通过不断应用状态转移方程，最终达到我们想要的结果。

说的更直白一点：
也就是说，如果我在做题的过程中，搞清楚了什么是子问题，还有初始状态，知道下一个状态该如何正确计算。那么我就能从这个初始状态直接往后推，直到推出最后的正确答案。

然后就立马写出了这个题。感觉还是非常清楚的。
子问题怎么找? 这里我看网上一般是通过推广的办法,由f(n)来思考那么是要计算f(n-1)+f(n-2)。那么推广到i就是dp[i] = dp[i-1]+dp[i-2];所以子问题就是计算dp[i-1]和dp[i-2]。往最初的状态倒就是从dp[0] 和 dp[1]开始
状态转移方程是啥？ 就是怎么计算下一个状态，这里状态转移方程就是dp[i] = dp[i-1]+dp[i-2]
最终状态怎么确定？ 就是看dp要到哪停下来。这里就是算dp[n]

dp数组到底怎么初始化？这个我认为一是要根据问题，而是要根据数据的边界。即最大可能取到的状态来确定长度。

class Solution {public int fib(int n) {//快速特判if(n<2){return n;}int[] dp = new int[n+1];dp[0] = 0;dp[1] = 1;for(int i = 2;i<=n;i++){dp[i] = dp[i-1]+dp[i-2];}return dp[n];}
}

提交之后会发现，效率和备忘录那个写法的效率相同
因为这俩的计算纯粹是反过来的关系

然后还可以再进一步优化

是不是发现我们其实只要这个最后的dp[n]，甚至感觉这个dp数组有点多余了。
确实是，我们其实就只需要不断的迭代更新后面两个数字 即 dp[i-1] 和 dp[i-2]
这个技巧就是所谓的状态压缩 空间复杂度直接优化为o1了。
怎么理解状态压缩的应用？就是想想原来的dp数组，有没有一些空间是不必要存储的。

所以这里还有一个究极版本。

class Solution {public int fib(int n) {if(n<2){return n;}int pre = 0;int cur = 1;for(int i = 2;i<=n;i++){//sum是下一个状态int sum = pre+cur;pre = cur;cur = sum;}return cur;}
}

零钱兑换

上面的斐波那契还体现不出dp。因为没有求最值问题，现在来看看这个题。
我第一想法就是一个大回溯直接爆搜。果不其然第32个例子直接超时。

接下来就只能看看题解了，用dp来做这个题。

这里得到第一个知识点：能用dp，首先要复合最优子结构，子问题间必须互相独立。
啥叫互相独立，就是子问题之间没有互相影响。
简单来说就是考试，你要拿最高分，比如一共两名，语文和数学。
要拿最高分就是数学考最高，语文考最高。这样就叫独立。
如果你数学考得高了，会导致你语文考不高，那就不叫独立。

所以要自己看看子问题之间有没有互相制约关系，是否相互独立

还有这个看待子问题的角度也非常重要。有时候你子问题找错了，那就可能做不出来了。
对于本题而言，子问题是这样拆分的，比如追求amont = 11（原问题），如果你知道凑出amont = 10的最少硬币数（子问题），那么只需要把子问题的答案（再选一枚面值为1的硬币），就是原问题的答案。还有这怎么看出子问题之间没有互相限制，因为硬币数量是没有限制的。

这里又纠正了我看待动态规划问题的思路了。一开始我是没理解倒这个问题中的独立。
1、动态规划的思考方向：
首先，动态理解是要自底向上思考的，而不是从amount=11开始往下想，我从大的开始想，那么我就会老是去想我最后一个面值为1了，那不是有可能对我前面的问题产生影响？
这里主要是方向想错了
2、子问题的定义：
对于金额i，子问题是凑出金额i所需的最少硬币数
3、独立性本质：
当我们说子问题是独立的，我们指的是，求解金额i的最优解，不依赖于如何求解i+1，i+2等更大的金额。（说白了还是方向看错了）。
4、为什么看起来不独立（我之前的思想）：
因为我方向想反了。

现在来模拟这个问题
举例说明：
假设硬币面值为 [1, 2, 5]，我们要凑出 11。

我们首先解决小额问题：1, 2, 3, 4, 5, …
当我们到达 11 时，我们考虑的是：
dp[11] = min(dp[10] + 1, dp[9] + 1, dp[6] + 1)
这里的 dp[10], dp[9], dp[6] 都已经是各自最优的解了
我们不是在考虑 “用1个1硬币然后解决10”，而是在比较 “10的最优解+1” 和其他可能性

独立性的证明：

如果 dp[10] 是最优的（假设是3个硬币），那么无论我们如何解决 11，都不会影响 10 的这个最优解。
即使我们选择了 “dp[9] + 1个2硬币” 作为 11 的最优解，这也不会改变 10 的最优解仍然是 3 个硬币这个事实。

198 打家劫舍

这个题我对动态规划又有了新的见解。
首先上面在斐波那契数列的理解非常重要。

我目前认为想到动态规划的递推写法应该是有一个过程的，而不是一些题解上来就说有这样的状态转移的过程。

在这个题里，我总结为五步走：
1、寻找子问题（寻找子问题，围绕两点，1、要么从前往后看，要么从后往前看，大多数的题从后往前看要比较好找子问题，因为从后看就是将大问题转换为小问题来思考。2、状态定义、状态转移方程一般通过“选或者不选”或者“选哪个”这两种思路来推导）
2、递归怎么写（状态定义和状态转移方程），画递归树
3、递归+记录返回值=记忆化搜索（搞个hash，计算重复）
4、1：1翻译成递推（将递去掉，只保留归，自底向上计算），将dfs改写成dp数组，对初始值做特殊处理。
5、空间优化（有一些状态用过之后，就不再需要了，可以从这个点实现优化，在递推的过程永远只更新计算下一个状态需要的状态）

现在正式来看题。
比如现在4个房子

1、从后往前看，对于最后一个房子
如果不选，那么就变成前n-1个房子的问题
如果选，那么就变成前面n-2个房子的问题（题目说不能相邻）。
然后这样依次的往前推，那么很容易得到这样的递归图。

2、
那么现在就可以推导，当我们推广到选第i个房子的情况，选或者不选，所产生的问题的结果就是
dfs(i) = max(dfs(i-1),dfs(i-2)+nums[i])。这样就得到了一个公式，这个也被称之为该问题一般情况下的状态转移方程。当然这个状态转移方程还不完整，它还缺少了一些特殊状态的值的计算（也就是初始状态值）。

3、基于递推图，那么可以发现里面有重复计算的地方，这个时候优化就是弄一个hash或者说叫备忘录来存储计算过的值，当之后要进行计算时，先去备忘录看看有没有现成的。
然后对这个图进行优化，把有重复的地方都干掉，即某个点如果有现成的，那么把它的分支全干掉，这代表不用往下面递归去计算了。

最左边这条路肯定是要的，自己递归模拟一下。

4、翻译成递推
0和1归到2 ，2和1归到3，3和2归到4。

现在相当于知道要从哪些点归到哪个点能计算后面的状态。就干脆去掉了递的过程，只留归。
那么现在从底向上，就叫递推了

现在如何改dfs改写成递推？
1、把dfs改写成f数组
dfs(i) = max(dfs(i-1),dfs(i-2)+nums[i])
f[i] = max(f[i-1] ,f[i-2]+nums[i])
2、把递归改成循环
然后对越界不合法的地方特殊处理一下，然后使得开始位置处于合法就可以往后推了。比如这里就需要i改成2或者3开始，这样才合法。对i=0，i=1的情况进行特殊处理。循环停下来的地方就是你想要的f(i)的地方就可以了。

5、空间优化。
从递推式里面可以看出来，计算前f[i]永远只需要前两个状态，f[i-1]和f[i-2]，那么在迭代的过程中不断把这两个状态存下来就可以了。这样dp数组直接不需要了。
f0 = 上上个状态
f1 = 上个状态
newF = max(f1,f0+nums[i])
下一个迭代
f0 = f1
f1 = newF

写代码我就直接写4和5的
这个是按着思路直接来写的。看着也许有点啰嗦

class Solution {public int rob(int[] nums) {int n = nums.length;//特殊情况判断if(n==1){return nums[0];}if(n == 2){return Math.max(nums[0],nums[1]);}int[] dp = new int[n];//初始状态dp[0] = nums[0];dp[1] = Math.max(nums[0],nums[1]);for(int i = 2;i<n;i++){dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);}return dp[n-1];}
}

进一步优化空间，只存前两个状态

改写也是非常的容易，因为是从初始状态来的，那么前两个状态就是dp[0]和dp[1]现在把这俩换成常量就行了。比如cur和pre，然后循环里面表示前面状态的给替换成现在的变量就行了。

class Solution {public int rob(int[] nums) {int n = nums.length;if(n==1){return nums[0];}if(n == 2){return Math.max(nums[0],nums[1]);}int pre = nums[0];int cur = Math.max(nums[0],nums[1]);for(int i = 2;i<n;i++){int next= Math.max(cur,pre+nums[i]);pre = cur;cur = next;}return cur;}
}

70 爬楼梯

我感觉现在强的离谱，再来看这个题。
感觉就是一个模板

1、直接从后面看，假设n=9
最后一步往前推，有两种情况要么最后一步爬1阶，要么最后一步爬两阶。

那么这个子问题拆分应该是：
子问题1：到i-1阶的所有方法再+1步
子问题2：到i-2阶的所有方法再+2步
我刚开始写到这我还想了想，这到底独不独立。因为我想i-1和i-2前面的走法是不是有重叠，当然不会有重叠，凭借这多+1步或者多+2步的决策，就不可能是重叠。

那么可以写出递归表达式
dfs(i) = dfs(i-1) + dfs(i-2)
然后做一下边界处理。即i即将为负数的时候，当i = 0，那显然就是1，因为0阶到0只有一种方法，就是原地不动。故1种爬法
当i = 1 那么就是1种爬法。爬一个台阶。
由于现在我心里已经有这样一幅图。那我感觉我可以不写dfs直接写dp了

那我立马把dfs换成dp。状态转移方程就是子问题相加
dfs(i) = dfs(i-1) + dfs(i-2) 改成dp。然后做做边界处理
dp[i] = dp[i-1]+dp[i-2]
dp[0] = 1 dp[1] = 1

那么代码有了

class Solution {public int climbStairs(int n) {//快速特判if(n == 1){return 1;}int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;for(int i = 2;i<=n;i++){dp[i] = dp[i-2]+dp[i-1];}return dp[n];}
}

空间优化
就是改写前两个状态。

class Solution {public int climbStairs(int n) {if(n == 1){return 1;}int pre = 1;int cur = 1;for(int i = 2;i<=n;i++){int next  = pre + cur;pre = cur;cur = next;}return cur;}
}