动态规划算法及其经典问题求解（Java）_算法经典问题

1、动态规划算法

动态规划算法(Dynamic Programming)，也叫dp算法，该算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解；

2、动态规划&分治

动态规划和分治法相似，都是通过组合子问题的解来求解原问题。分治法将问题划分成互不相交的子问题，递归求解子问题，再将他们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。在这种情况下，分治算法会做出许多不必要的工作，它会反复的求解那些公共子问题。而动态规划算法对每个子子问题只求解一次，将结果保存到表格中，从而无需每次求解一个子子问题都要重新计算。
https://blog.csdn.net/u013309870/article/details/75193592
https://blog.csdn.net/a962035/article/details/79943708

3、动态规划算法典型例题

3.1选数问题

题目要求：
假设给定一串数字{1, 2, 4, 1, 7, 8, 3}，我们要从中选择若干个数，使最后的和达到最大。选择的规则是，不能选相邻的数字。比如：如果我们选了第一个数字1，那么我们就不能选2，如果我们选择了数字4，那么我们就不能选择与它相邻的2和1。

动态规划的思想：
将整个问题划分成一个个子问题，也就是说要求整个数列的最大和，可以先求出前面若干个数的和，一直划分到求出只有一个数的最大和（即本身），而每个子问题的解对于后面的结果都是有用的，这就是用到了动态规划的思想

思路：
对于每个数，都有选和不选两种状态，如果选了这个数，那么就不能选他相邻的那个数，那么最大和就等于本身加上他相邻的那位数之前那些数的最大和，如果不选这个数，那么便可以选它相邻的那个数，那么最大和就等于这个数之前的那些数的最大和。最终的结果就是取这两种选择的最大值

这里就可以使用递归，即Math.max(dp(arr, x-2)+arr[x], dp(arr, x-1))；

递归的出口：

• 如果只有一个数，那么最大和就是本身
• 如果只有两个数，那么最大和就是这两个数中的最大值

3.1.1递归解法

/**
* 动态规划之选数问题:递归解法
* @param arr：将给定的一串数字放在数组中
* @param x：数组下标，也就是求出数组第一个元素到这个下标之间的最大和
* @return
*/
public static int dp(int[] arr,int x){
    if(x==0){
        return arr[0];
    }
    if(x==1){
        return Math.max(arr[0], arr[1]);
    }
    return Math.max(dp(arr, x-2)+arr[x], dp(arr, x-1));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.1.2动态规划解法

由于递归会重复计算相同的值，所以我们这里使用非递归解法，也就是创建一个数组来保存计算过的值，由此提高效率。例如temp[0]用来保存数组中只有一个数的最大和，temp[1]用来保存数组中只有两个数的最大和；temp[arr.length()-1]用来保存整个数组的最大和

/**
     * 动态规划之选数问题:非递归解法
     *
     * @return
     */
    public static int dp(int[] arr) {
        int[] temp = new int[arr.length];
        temp[0] = arr[0];
        temp[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < arr.length; i++) {
            temp[i] = Math.max(temp[i - 2] + arr[i], temp[i - 1]);
        }
        return temp[arr.length - 1];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.2最长公共子序列

最长公共子序列问题：longest common subsequence，也叫LCS问题，是动态规划算法的经典例题；解题步骤类似于背包问题，通过创建一个二维数组，并逐步进行填充，通过填表，总结出此问题的公式！

题目描述：
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

/**
* 动态规划之最长公共子序列
* @return
*/
public static int longestCommonSubsequence(String text1, String text2) {
    int len1=text1.length();
    int len2=text2.length();
    char[] ch1=text1.toCharArray();
    char[] ch2=text2.toCharArray();

    //动态规划算法创建的二维数组一般都得多增一行一列，这是为了防止数组越界异常
    int[][] p=new int[len1+1][len2+1];

    //填表，第一行和第一列都为0，所以填表从下标为1的行和下标为1的列开始填
    for(int i=1;i<p.length;i++){
        for(int j=1;j<p[0].length;j++){
            if(ch1[i-1]==ch2[j-1]){
                p[i][j]=p[i-1][j-1]+1;
            }else{
                p[i][j]=Math.max(p[i-1][j], p[i][j-1]);
            }
        }
    }	
    return p[len1][len2];
}

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

3.3钢条切割问题

3.3.1递归解法

/**
     * @param p 长度-价格
     * @param n 钢条长度
     * @return 最大收益
     */
    public static int cut(int[] p, int n) {

        if (n == 0)
            return 0;
        int q = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            q = Math.max(q, p[i - 1] + cut(p, n - i));
            System.out.println(q);
        }
        return q;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.3.2动态规划解法

  public static int buttom_up_cut(int[] p, int n) {
        int[] r = new int[p.length + 1];
        for (int i = 1; i <= n; i++) {
            int q = -1;
            for (int j = 1; j <= i; j++)
                q = Math.max(q, p[j - 1] + r[i - j]);
            r[i] = q;
        }
        return r[n];
    }
1
2
3
4
5
6
7
8
9
10

3.4斐波那契数列

3.4.1递归解法

public int fib(int n)
{
	if(n<=0)
		return 0;
	if(n==1)
		return 1;
	return fib( n-1)+fib(n-2);
}
//输入6
//输出：8


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

3.4.2递归解法

public static int fib(int n)
	{
		if(n<=1)
			return n;
		
		int Memo_i_2=0;
		int Memo_i_1=1;
		int Memo_i=1;
		for(int i=2;i<=n;i++)
		{
			Memo_i=Memo_i_2+Memo_i_1;
			Memo_i_2=Memo_i_1;
			Memo_i_1=Memo_i;
		}		
		return Memo_i;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.5背包问题（0-1背包）

https://www.bilibili.com/video/BV1Mf4y1y7WD/?spm_id_from=333.337.search-card.all.click&vd_source=52f9eb63aa834f8c039c3dedc7463736
题目描述：

public static void main(String[] args) {
        int[] w = {2, 2, 6, 5, 4};//物品的重量，分别表示吉他1磅，音响4磅，电脑3磅
        int[] v = {6, 3, 5, 4, 6};//物品的价值，分别表示吉他1500，音响4000，电脑3000

        int m = 10;//背包的容量
        int n = w.length;//物品的个数

        //创建一个二维数组
        int[][] p = new int[n + 1][m + 1];//将物品多增一行和背包的容量多增一列是为了防止后面的公式出现数组越界异常

        //填表，注意是从下标为1的那一行以及下标为1的那一列开始填的
        for (int i = 1; i < p.length; i++) {
            for (int j = 1; j < p[0].length; j++) {
                //因为下标是从1开始，所以w数组的下标要减一
                if (j < w[i - 1]) {
                    //将上一行对应列的单元格的值赋给当前位置
                    p[i][j] = p[i - 1][j];
                } else {
                    //j>=w[i-1]的情况

                    //p[i-1][j]表示上一行对应列的单元格的值，也就是没有新增当前商品之前对应重量的最大价值
                    //v[i-1]表示当前商品的价值，注意下标也是要减一
                    //j-w[i-1]表示当前容量减去当前物品的容量后剩余容量
                    //p[i-1][j-w[i-1]]表示没有加入当前商品前剩余这个容量对应的最大价值
                    p[i][j] = Math.max(p[i - 1][j], v[i - 1] + p[i - 1][j - w[i - 1]]);
                }
            }
        }

        //输出填写的二维数组
        for (int i = 0; i < p.length; i++) {
            for (int j = 0; j < p[0].length; j++) {
                System.out.print(p[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println("能装入的最大价值为：" + p[p.length - 1][p[0].length - 1]);
    }
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
36
37
38