动态规划入门详解java实现_动态规划java实现

一到经典且简易的动态规划问题

              5      //表示三角形的行数    接下来输入三角形

              7

            3   8

         8    1    0

       2    7    4    4

     4    5    2    6    5
1
2
3
4
5
6
7
8
9
10
11

在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。 三角形的行数大于1小于等于100，数字为 0 - 99。

一般的递归解决方案

首先我们用二维数组将这个三角形装起来。数组中只能往右下走，并不能往左下走。在数组中我们可以把往左下走看做往下走，结构如下。
*
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
*

代码实现还是相对简单的，一直递归调用就可以了。代码如下：
仔细看其中有过多的重复步骤，比如D（3,1）= 8，我们在算MaxSun（3,1）的时候计算了一遍，然后在计算MaxSun（2,1）的时候又再次计算一遍。这些大量的重复步骤，导致程序效率低下。
那么这种算法的时间复杂度是多少呢？
子问题执行时间(O(1))乘子问题个数(2^(n-1))
时间复杂度为_O(2^n)_。这个时间复杂度有些太大了。

public class Solution {
	
	public int  getMax(int[][] a) {
		int n = a.length - 1;
		int i = 0;int j = 0;
		int maxSum = getMaxSum(a,n,i,j);
		return maxSum;
	}

	private int getMaxSum(int[][] a, int n, int i, int j) {
		//当数为最后一排的时候
		if (i == n) {
			return a[i][j];
		}
		int x = getMaxSum(a, n, i+1, j);
		int y = getMaxSum(a, n, i+1, j+1);
		return Math.max(x, y) + a[i][j];
	}
	
	public static void main(String[] args) {
		
		int [][]a =new int [][]{{7},
					            {3,8},
					            {8,1,0},
					            {2,7,4,4},
					            {4,5,2,6,5}};
		
		Solution solution = new Solution();
		int max = solution.getMax(a);
		System.out.println(max);
		
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

使用动态规划来解决问题

1.什么是动态规划呢

动态规划的大致思路是把一个复杂的问题转化成一个分阶段逐步递推的过程，从简单的初始状态一步一步递推，最终得到复杂问题的最优解。

2.使用动态规划解决问题的要素

1.最优子结构（一个问题的最优解，包含其子问题的最优解）
2.子问题重叠

在上述问题中，MaxSum(r, j)的最优解，一定包含MaxSum（r + 1，j）或者MaxSum（r + 1，j + 1）的最优解，且问题具有重复性，不断递归调用。从这两点要素看来，该问题可以使用动态规划求解

2.使用动态规划解决问题的步骤

1.寻找状态转移方程式（包括边界）
3.利用状态转移方程式自底向上求解问题

这个只是简化后的步骤可以帮助入门，寻找状态方程是最重要的一点，本题的状态方程如上图的if与else部分。

那么什么是自底向上呢？上面我们已经分析过了单单只使用递归造成程序效率低下的原因。我们可以看到上述递归方式是自上而下的解决思路。程序一直递归到倒数第二排，我们才开始确定倒数第二排几个数的MaxSum。因为最后一排的MaxSum是确定的，就是自己。我们可以把最后一排的几个数看做边界。

动态规划使用的是自底向上的思路，由于最后一排的MaxSum是确定的，我们就可以从最后一排开始。

解题思路如下：
初始化一个和最后一行一样大小的数组，也将值复制给它，也就是初始化为arr=[4,5,2,6,5]，首先我们找到arr 中相邻两个节点中最大的那个，接着加上相邻两个元素的父节点，例如最后一行4,5的父节点是2，那么第一次循环后就得到 arr=[7,5,2,6,5]，接着是5,2和7，继续更新为arr =[7,12,2,6,5]…以此类推。这样就可以不断的向上一层进行循环，一直到第一层，最终arr[0]位置的元素便是最大值

代码如下：

public int getMaxSum2(int[][]a) {
		int n = a.length - 1;
		int[] arr = a[n];
		for(int i = n - 1;i >= 0;i --) {
			for(int j = 0;j <= i;j ++) {
				arr[j] = Math.max(arr[j],arr[j + 1]) + a[i][j];
			}
		}
		return arr[0];
	}
1
2
3
4
5
6
7
8
9
10

时间复杂度：(子问题个数x子问题的时间复杂度）为O（n²）

一些补充和说明

本人也是最近在学动态规划，对于一些错误和不足的地方欢迎改正。这篇文章只是动态规划的入门，动态规划的一些分析和解题步骤都没有写出来，因为对于初次接触的比较难以理解。

第一种解题方案还有一种优化的方法，备忘录法，既然我重复计算很多，那么我可以在第一次计算的时候把数值记录到数组中，等到第二次用到的时候我就去数组中去找。这样优化后时间复杂度也为O(n²）。具体代码可以自己写一下。
动态规划问题如何找解题思路呢？有一个不聪明的办法，但是也适用很多动态规划的问题。

首先用暴力一点的思路来想怎么解决问题比如穷举，比如递归。有了解决问题的思路，然后我们可以使用备忘录法来优化，或者使用自底向上的方式来优化，这样也能极大的提高效率

动态规划问题还是比较难的，入门之后可以多做一些题，看大佬的博客，来加深完善自己对动态规划问题的理解。