什么是动态规划
前言
招聘结束，结合笔试题给大家分享一下动态规划，LZ最近在GitHub上分享了2个项目一个用是netty实现http服务，还有就是RPC框架Thrift的使用，点下面原文链接即可跳到LZ的GitHub，每个项目的思路都写了博客详细介绍，感兴趣的小伙伴可以给LZ发merge request
笔试题1
题目来源：LeetCode 62不同路径
题目描述：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
示例：输入: m = 3, n = 2，输出: 3
解释:从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
思路：这个大家一下就会想到用递归解决，假设f(m,n)表示移动到点(m,n)的路径书，因为机器人智能向下或者向右移动，所以点(m,n)只能从点(m-1,n)和(m,n-1)移动而来，递归公式就是f(m,n)=f(m-1,n)+f(m,n-1)，递归的出口呢？当然就是网格的边界了，网格边界上的点都只有一种方法，按照这种思路写出来如下代码
class Solution {
public int uniquePaths(int m, int n) {
// 在网格边界的格子只能有一种走法
if (m == 1 || n == 1) {
return 1;
}
// m，n这个位置只能从(m - 1 , n)和(m, n - 1)移动而来
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}其实这个代码效率还是很低的，因为有很多重复的计算，如下图
当m和n为(3,3)时，(2,2)被计算了2次，而且m和n越大，重复计算的次数最多，我们可以把已经算出来的值保存一下，这样下次再用的时候就不用算了，直接取就行，叫做备忘录算法，grid[m][n]表示走到（m,n）这个点时的路径数。
class Solution {
public static int[][] grid = new int[110][110];
public int uniquePaths(int m, int n) {
if (grid[m][n] != 0)
return grid[m][n];
if (m == 1 || n == 1) {
return 1;
}
return grid[m][n] = uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}
}当值不为0的时候说明已经被算过了，直接取就行了，否则就得计算并保存结果，这样效率提高了不少，但是如果m和n特别大，递归层数过多时会造成堆栈溢出的，该怎么办？这个时候就得用到动态规划了
递归是从上至下开始计算的，有没有可能从下而上的计算呢？，如先算出（1，2）和（2，1），然后就能算出（2，2）了，我们得按照一定的规律计算，保证在算（2，2）之前，（1，2）和（2，1）已经算完了，我们只要按行从左到右计算，或者按列从上到下即可
class Solution {
public static int[][] grid = new int[110][110];
public int uniquePaths(int m, int n) {
for (int i = 1; i <= n ; i++) {
for (int j = 1; j <= m ; j++) {
if (i == 1 || j == 1)
grid[i][j] = 1;
else
grid[i][j] = grid[i][j-1] + grid[i-1][j];
}
}
return grid[n][m];
}
}动态规划并不是一种具体的算法，而是一种思想，把求解的问题分成许多阶段或者多个子问题，然后按顺序求解各子问题。前一子问题的解为后一子问题提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
面试题2
题目来源：《剑指offer》第二版
题目描述：给你一根长度为n的绳子，请把绳子剪成m段 (m和n都是整数，n>1并且m>1)每段绳子的长度记为k[0],k[1],…,k[m].请问k[0]k[1]…*k[m]可能的最大乘积是多少？例如，当绳子的长度为8时，我们把它剪成长度分别为2,3,3的三段，此时得到的最大乘积是18.
思路：定义函数f(n)为长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀的时候，我们有n-1种可能的选择，也就是剪出来的第一段绳子的长度分别为1,2...n-1。因此f(n)=max(f(i)*f(n-i))，其中0<i<n。这是一个从上至下的递归公式，递归会有很多重复的子问题。我们可以从下而上的顺序计算，也就是说我们先得到f(2)，f(3)，再得到f(4)，f(5)，直到得到f(n)
public class Solution {
public int maxNumAfterCutting(int n) {
if (n < 2)
return 0;
// 绳子长度为2时，只能剪成1和1
if (n == 2)
return 1;
// 只可能为长度为1和2的2段或者长度都为1的三段，最大值为2
if (n == 3)
return 2;
// 当长度大于3时，长度为3的段的最大值时3
int product[] = new int[n+1];
product[0] = 0;
product[1] = 1;
product[2] = 2;
product[3] = 3;
int max = 0;
for (int i = 4; i <= n; i++) {
max = 0;
for (int j = 1; j <= i / 2; j++) {
int sum = product[j] * product[i - j];
if (sum > max) {
max = sum;
product[i] = max;
}
}
}
return product[n];
}
}代码中第一个for循环变量i是顺序递增的，这意味着计算顺序是自下而上的。因此再求f(i)之前，对于每一个j(0<i<j)而言，f(j)都已经求解出来了，并且保存在product[j]里。为了求解f(i)，我们需要求出所有可能的f(i)*f(i-j)并比较得出他们的最大值，这就是代码中第二个for循环的功能
这个面试题又比第一个面试题难了一点，因为第一个面试题仅仅是将一个大问题划分成几个子问题，并没有根据局部解进行决策得到最优解，而这个面试题体现了决策的过程
面试题3
题目来源：LeetCode 42. 接雨水
题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）
示例：
输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6
思路：这个单纯的遍历其实也能出来，但是要考虑的情况比较多，对每一个柱子能存多少水求和这种方法比较简单，这样只需要获取这个柱子左边的最高高度和这个柱子右边的最高高度，2者的最小值减去柱子的高度就是这个柱子的存水量
class Solution {
public int trap(int[] height) {
int sum = 0;
for (int i = 0; i < height.length; i++) {
int maxLeft = 0, maxRight = 0;
for (int left = 0; left < i; left++) {
maxLeft = Math.max(maxLeft, height[left]);
}
for (int right = i + 1; right < height.length ; right++) {
maxRight = Math.max(maxRight, height[right]);
}
int temp = Math.min(maxLeft, maxRight) - height[i];
if (temp > 0)
sum += temp;
}
return sum;
}
}每次都要算某个柱子的左右最值，时间复杂度是O(n2)，能不能把算左右最值的效率提高呢？这就用到动态规划了，假如说
我们用函数f(n)，表示到第n个柱子（包括第n个柱子）左边的最大值，则f(n)=max(f(n-1)，height[n])，其中height[n]为第n个柱子的高度，右边同理
class Solution {
public int trap(int[] height) {
int sum = 0;
int len = height.length;
if (len == 0)
return 0;
int[] maxLeft = new int[len];
int[] maxRight = new int[len];
maxLeft[0] = height[0];
for (int i = 1; i < len; i++) {
maxLeft[i] = Math.max(height[i], maxLeft[i-1]);
}
maxRight[len - 1] = height[len - 1];
for (int i = len - 2; i >= 0; i--) {
maxRight[i] = Math.max(height[i] ,maxRight[i+1]);
}
for (int i = 0; i < height.length; i++) {
sum += Math.min(maxLeft[i], maxRight[i]) - height[i];
}
return sum;
}
}这样时间复杂度就变成O(n)了
后记
上面几个例子都是写了几个方程，然后根据这个方程写出了代码，这个公式叫做状态转移方程，只要能写出状态转移方程，就能很快写出代码，对动态规划感兴趣的可以看一下动态规划的经典实现，最长上升子序列，最长公共子串，数塔问题，背包问题等