1. 简介

动态规划是为了优化暴力尝试的。

2. 求n!

2.1 一般思路

public static long getFactorial2(int n) {
	long result = 1L;
	for (int i = 1; i <= n; i++) {
		result *= i;
	}
	return result;
}

2.2 递归

• 要求n!，求出(n-1)!，再乘以n即可；
• 求(n-1)!，先求出(n-2)!，再乘以(n-1)即可；
• ...
• 需要有个Base case，即n=1时，不再递归，直接返回1。

即：n!的结果依赖于n-1；n-1依赖于n-2；...；2依赖于1。

计算的时候，将顺序逆过来，由1得到2，再得到3，...，再得到n-1，得到n。

一般方法的思路：把不依赖于别的的状态给出，然后计算依赖于它的的状态，在往后计算

public static long getFactorial1(int n) {
	if (n == 1) {
		return 1L;
	}
	return (long) n * getFactorial1(n - 1);
}

3.汉诺塔问题

打印n层汉诺塔从最左边移动到最右边的全部过程

3.1 简介

如图：

将左杆上的盘全部移到右杆上，中杆可作为辅助，要求大盘不能压小盘。

3.1.1 具体步骤

3.2 递归思路分析

有from，to，help三个杆，1~N个盘在from杆上，需把它们移到to杆上。可以利用help杆。

1. 需把1~n-1从from挪到help上；
2. 把单独的n挪到to上；
3. 把1~n-1从help挪到to上；

package Recursive;

public class Hanoi {
	public static void main(String[] args) {
		hanoi(3,"左","右","中");
	}
	
	public static void hanoi(int N,String from,String to,String help) {
		if(N==1)
			System.out.println("Move "+N+" from "+from +" to "+to);
		else {
			hanoi(N-1,from,help,to);
			System.out.println("Move "+N+" from "+from +" to "+to);
			hanoi(N-1,help,to,from);
		}
	}
}

运行结果：

3.3 将上述递归过程拆为6个子过程

1. L->R
2. L->M
3. R->M
4. R->L
5. M->L
6. M->R

L->R（M作为辅助）具体包括：

1. L->M：1~N-1   
2. L->R：N     
3. M->R：1~N-1    

L->M（R作为辅助）具体包括：

1. L->R：1~N-1
2. L->M：N
3. R->M：1~N-1

后面四个步骤类似。

3.4 代码实现

package Recursive;

public class Hanoi {
	public static void main(String[] args) {
		moveLeftToRight(3);
	}

	public static void moveLeftToRight(int N) {
		if(N==1)
			System.out.println("Move "+N+" from 左  to 右");
		else{
			moveLeftToMiddle(N-1);
			System.out.println("Move "+N+" from 左  to 右");
			moveMiddleToRight(N-1);
		}
	}
	
	public static void moveLeftToMiddle(int N) {
		if(N==1)
			System.out.println("Move "+N+" from 左  to 中");
		else{
			moveLeftToRight(N-1);
			System.out.println("Move "+N+" from 左  to 中");
			moveRightToMiddle(N-1);
		}
	}
	
	public static void moveMiddleToRight(int N) {
		if(N==1)
			System.out.println("Move "+N+" from 中  to 右");
		else{
			moveMiddleToLeft(N-1);
			System.out.println("Move "+N+" from 中  to 右");
			moveLeftToRight(N-1);
		}
	}
	
	public static void moveRightToMiddle(int N) {
		if(N==1)
			System.out.println("Move "+N+" from 右  to 中");
		else{
			moveRightToLeft(N-1);
			System.out.println("Move "+N+" from 右  to 中");
			moveLeftToMiddle(N-1);
		}
	}
	
	public static void moveRightToLeft(int N) {
		if(N==1)
			System.out.println("Move "+N+" from 右  to 左");
		else{
			moveRightToMiddle(N-1);
			System.out.println("Move "+N+" from 右  to 左");
			moveMiddleToLeft(N-1);
		}
	}
	
	public static void moveMiddleToLeft(int N) {
		if(N==1)
			System.out.println("Move "+N+" from 中  to 左");
		else{
			moveMiddleToRight(N-1);
			System.out.println("Move "+N+" from 中  to 左");
			moveRightToLeft(N-1);
		}
	}
}

4.打印字符串的子序列（不是子串），包括空序列

4.1 分析

每走一步，都有两个决策：

• 加当前位置上的字符
• 不加这个字符

4.2 代码实现

package Recursive;

public class PrintAllSub {
	public static void main(String[] args) {
		String str="abc";
		printAllSub(str.toCharArray(),0,"");
	}
	
	public static void printAllSub(char[] str,int i,String res) {
		if(i==str.length) {
			System.out.println(res);
			return;
		}
		printAllSub(str,i+1,res);
		printAllSub(str,i+1,res+str[i]);
	}
}

运行结果：

5.打印一个字符串的全排列

5.1 分析

第一步：确认第一个位置的字符，即第一个位置的字符一次和后面位置的字符进行交换

第二步：确认第二个位置的字符，...

...

最后，知道表示位置的index=字符串长度时，打印。

5.2 代码实现

package Recursive;

public class PrintAllPermutations {
	public static void main(String[] args) {
		String str="abc";
		printAllPermutations(str);
	}
	
	public static void printAllPermutations(String str) {
		char[] chs=str.toCharArray();
		process(chs,0);
	}
	
	public static void process(char[] chs,int i) {
		if(i==chs.length) {
			System.out.println(chs);
			return;
		}
		else {
			for(int j=i;j<chs.length;j++) {
				swap(chs,i,j);
				process(chs,i+1);
				swap(chs,i,j);//回归原始位置，继续下一轮交换
			}
		}
	}
	
	public static void swap(char[] chs, int i,int j) {
		char temp=chs[i];
		chs[i]=chs[j];
		chs[j]=temp;
	}
}

运行结果：

6.母牛生小牛

母牛每年生一只母牛，新出生的母牛成长三年后也能每年生一只母牛，假设牛不会死。

求N年后，母牛的数量。

6.1 分析

规律：

原因：第N年的牛个数=第N-1年牛的个数（牛不会死，去年的牛会保留到今年来）+向前数三年的牛的个数（新生的牛=可以生牛的母牛个数）

做法：写出前几项，得出规律，看规律是否合理。

时间复杂度：

有个更优的，时间复杂度为

• 利用线性代数中矩阵乘法来解。
• 斐波那契数列也存在的解

7.暴力递归试出动态规划——最小路径和

给一个二维数组，其中的每个数都是正数。要求从左上角走到右下角，每一步只能向右或者向下。沿途经过的数字要累加起来，返回最小的路径和。

7.1 递归版本

package Recursive;

public class MinRoadSum {
	public static void main(String[] args) {
		int[][] arr= {{3,2,1,0},{7,5,0,1},{3,7,6,2}};
		System.out.println(minRoadSum(arr));
	}
	
	public static int minRoadSum(int[][] arr) {
		
		 int res=process(arr,0,0);//当前数组，当前的行号，当前列号，当前路径和
		 return res;
	}
	
	//从(i,j)出发，到达右下角的位子
	public static int process(int[][] arr,int i,int j) {
		int hlen=arr.length-1;
		int llen=arr[0].length-1;
		
		if(i==hlen&&j==llen) 
			return arr[i][j];
		
		if(i==hlen)//只能往右走
			return arr[i][j]+process(arr,i,j+1);
		if(j==llen)//只能往下右走
			return arr[i][j]+process(arr,i+1,j);

		int down=process(arr,i+1,j);//下边位置到右下角的最短路径和
		int right=process(arr,i,j+1);
		return arr[i][j]+Math.min(down, right);
	}
}

这是暴力：

有大量重复解产生，如上图中的f(1,1)。

整个过程中，重复状态很多——暴力递归不行的原因。

7.2 改进

在求解子过程时，将结果保存，下次用到的时候直接拿，可减少计算量。

——把1-1作为一个key，将f(1,1)作为value，存入哈希表中

7.3 递归可以改为动态规划的要求

——在展开递归的过程中，有重复的计算，而且这个重复的状态与到达它的路径无关。

比如点(1,1)，它到右下角点的最短路径与(0,0)是通过哪条路径到达它的无关。

——这种问题叫做无后效性问题。——只要参数定了（如，1，1），返回值就确定了（f(1,1)是一定的）。

有后效性问题：汉诺塔问题、N皇后问题。——之前作出的选择会影响后面的决策。

上题中，i和j一旦确定，返回值就是确定的。那么可以将所有的返回值存在和路径数组大小一样的数组dp中。

• dp数组中位置(i,j)表示：路径数组中的位置(i,j)到右下角点的最短路径和。

我们要的最终结果是(0,0)位置的值，标为※，

然后看可以确定的位置的值——base case，即右下角位置的值，就是matrix中右下角位置的值0；

if(i==hlen&&j==llen) 
    return arr[i][j];

接着看设置不被依赖的值：最后一行和最后一列

如果在最后一行，则当前位置的值=当前matrix位置中对应的值+右边位置的最短路径和（即dp中此位置右边的值）

if(i==hlen)//只能往右走
    return arr[i][j]+process(arr,i,j+1);

if(j==llen)//只能往下右走
    return arr[i][j]+process(arr,i+1,j);

最后一列也一样：

接着分析一个普遍位置是怎么依赖的：

int down=process(arr,i+1,j);//下边位置到右下角的最短路径和
int right=process(arr,i,j+1);

return arr[i][j]+Math.min(down, right);

在当前(i,j)，它需要：

• 右边的位置：(i,j+1)
• 左边的位置：(i+1,j)
• 选两者中较小的

由于最后一行和最后一列已确定，则右下角位置的左上方的值就可以确定。它左边的位置也可以求出来：

中间的位置从右到左，再从下到上，依次推倒顶部，即可得到答案。

以上就是暴力递归改为动态规划的统一套路。

• 写出可变版本
• 分析可变参数
  • 哪些可变参数可以代表返回值的状态
  • 参数时几维的，dp就是一张几维表
• 在dp中标出最终需要的点
• 回到base case中，将完全不依赖的位置的值设置好
• 分析一个普遍位置需要哪些位置，逆着回去，就会说填表的顺序。

8.累加和是否可达到给定值

给定一个数组arr，其中的数全为正数。如果可以任意选择arr中的数字。能不能累加得到正数aim。返回true或false。

8.1 分析

和子序列一样

比如给定：

3，2，7，13

aim=9。是否能加到9？

f(0,0)：目前在0位置，形成的和是0；

可按照子序列的方法分析，在每个位置选择要不要前一个位置的数。

到最后一层的时候，如果发现有一个累加和为9，返回true，然后一直往上，每一层只要有一个true，则最后结果肯定为true。

8.2 代码实现

package Recursive;

public class IsHaveSum {
	public static void main(String[] args) {
		int[] arr= {1,4,8};
		int aim=12;
		System.out.println(isHaveSum(arr,0,0,aim));
	}
	
	public static boolean isHaveSum(int[] arr,int i,int sum,int aim) {
		if(i==arr.length)
			return sum==aim;
		return isHaveSum(arr,i+1,sum,aim)||isHaveSum(arr,i+1,sum+arr[i],aim);
	}
}

8.3 分析是否有后效性

一个序列为3,2,5,...：

• 选3，2，没选5，则是f(3,5)。
• 没选3，2，选了5，还是f(3,5)

所以是无后效性的。

3和5一旦确定，则返回值肯定确定。

(arr,i,sum,aim)：四个参数中，arr和aim是确定的，i和sum是变化的——二维表

• LEN：数组中元素的个数，i的最大值；
• SUM：数组中所有元素的和，sum的最大值。

f(i,sum)肯定可以装在上面两个参数形成的二维表中。

8.4 转换

8.4.1 找出最终需要的状态

8.4.2 找出基本状态

if(i==arr.length)//最后一行
    return sum==aim;

aim>SUM直接返回false；

aim<SUM，则在最后一列SUM对应的位置为T（True）

0~SUM之间是以1为单位递增的。

8.4.3 分析普遍状态

return isHaveSum(arr,i+1,sum,aim)||isHaveSum(arr,i+1,sum+arr[i],aim);

状态(i,sum)，依赖的状态有：

• (i+1,sum)：下一行正下面的状态；
• (i+1,sum+arr[i])：假设arr[i]=a，则指的是下一行正下方往右推a个单位的状态。

8.5 若给定数组中有负值

SUM的范围：负值之和~正值之和

注意下标的对应。

比如：3，-2，5

则SUM的范围：-2~8

下标的范围：0~10