初识动态规划

写在前面

先来一波维基百科定义:
动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

从斐波那契数列认识动态规划

我们先来复习下大学时候题目：

    求解对于输入整数n，求解斐波那契数列中第n个数字。

使用递归思路求解：

    我们可以用f(n)表示斐波那契数列第n个数字，则有
    1. 对于 n >= 2的输入，求解斐波那契数列第n个数字通过第n-1个数字+第n-2个数字得到，即f(n) = f(n -1) + f(n -2);
    2. 相应的，第n-1个数字即为 f(n-1) = f(n - 2) + f(n -3)
    .....
    3. 如此递归下去，而f(0) = 0, f(1) = 1，这就是递归终止条件。
    
public class DpTest1 {
    public static void main(String[] args) {
        for (int i = 0; i < 20; i++) {
            System.out.print(fibTest1(i) + " ");
        }
    }

    public static int fibTest1(int n)
    {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        else return fibTest1(n-1) + fibTest1(n - 2);
    }
}
    如上是同个递归求0 - 20的斐波那契数列的代码，看起来还不错，问题似乎解决了。

递归思路简单清晰，但是其在空间和效率上的缺陷也特别明显，这种缺陷随着数据规模的增大，表现得越来越明显：
我们对代码进行稍微的改写，分别计算第10、20、30、40、50个斐波那契数，并计算求解时花费的时间及递归调用次数：

public class DpTest1 {
        private static long fibCnt = 0;

        public static void main(String[] args) {
            for (int i = 10; i <= 50 ; i+= 10)
            {
                fibCnt = 0;
                long start = System.currentTimeMillis();
                System.out.println(fibTest1(i));
                long end = System.currentTimeMillis();
                System.out.println("求解第" + i + "个斐波那契数用时：" + (end -start) / 1000.0 + "s. 递归方法调用次数为：" + fibCnt + "次" );
            }

        }
        public static long fibTest1(int n)
        {
            fibCnt ++;
            if(n == 0)
                return 0;
            if(n == 1)
                return 1;
            else return fibTest1(n-1) + fibTest1(n - 2);
        }
    } 

通过运行结果可以看到，对于数据规模为50的一个递归求解，所需要的用时已经是我们难以接受的了，同时看递归调用的次数也看出，对空间的花费也是极大：

使用记忆化搜索对递归进行优化

对于在时间和空间上都基本呈指数增长的递归算法求解斐波那契数，我们能否对其进行优化？答案是肯定的。
    1. 我们用n=5来分析下，递归算法之所以如此费时和费空间的原因

从图中可以看出，我们计算f(5),需要计算1次f(4), 2次f(3), 3次f(2),还需要调用5次f(1)和3次f(0), 其中，有大量重复的调用和计算，因此浪费了大量的时间和空间。
2. 通过1的分析，我们尝试优化1中存在的重复计算和调用
> 定义一个长度为n + 1的int数组memory(当数据规模非常大时，可以替换成long)，memory[i]保存第i个斐波那契数。
> 每次递归调用f[i]时，先检查memory[i]是否已经有计算结果，如果有，读取memory[i]的值返回
> 如果memory[i]中还没有保存有f[i]的值，递归调用f[i -1] + f[i -2]计算结果，然后保存到memory[i]中，然后返回memory[i].

    改进后的代码如下
        
public class DpTest1 {
    private static long fibCnt = 0;
    public static void main(String[] args) {
        for (int i = 10; i <= 50 ; i+= 10)
        {
            //定义memory，并把每个元素赋予初值为 -1；
            long[] memory = new long[i + 1];
            for (int j = 0; j < i + 1; j++) {
                memory[j] = -1;
            }
            fibCnt = 0;
            long start = System.currentTimeMillis();
            System.out.println(fibTest1(i, memory));
            long end = System.currentTimeMillis();
            System.out.println("求解第" + i + "个斐波那契数用时：" + (end -start) / 1000.0 + "s. 递归方法调用次数为：" + fibCnt + "次" );
        }

    }
    public static long fibTest1(int n, long[] memory)
    {
        if(memory[n] != -1)//做递归调用之前，先判断当前n是否已计算过
        {
            return memory[n];
        }
        fibCnt ++;
        if(n == 0)
        {
            memory[0] = 0;
            return memory[0];
        }
        if(n == 1)
        {
            memory[1] = 1;
            return memory[1];
        }
        else
        {
            memory[n] = fibTest1(n-1, memory) + fibTest1(n - 2, memory);
            return memory[n];
        }
    }
}

可以看到，现在我们计算斐波那契数已经非常快了，同时调用递归方法的次数也变成了memory数组的长度了，即n+1，此优化递归算法的方法叫做 记忆化搜索。

初识动态规划

上述的记忆搜索算法优化后的递归方法，对于求解斐波那契数来说，无论是从时间复杂度还是从空间复杂度来说，都已经是一个很好的算法了，但是我们是否可以再用更加优秀的算法来求解呢，答案就是动态规划法。将原问题拆解成若干自问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案，这就是动态规划。

• 回到求解斐波那契数的问题，我们通过递归算法进行求解的时候，会产生很多需要重复计算和调用的第i个斐波那契数，这些重叠的斐波那契数就是这个原问题的重叠子问题。
• 为了解决重叠子问题，我们在上面使用了记忆化搜索方法，从n 到 0，我们自顶向下地计算f(i)的值，并保存到memory数组中。
• 如果我们用自底向上的方法去解决重叠子问题的话，即定义一个dp数组，dp数组中第i项记录第i个斐波那契数，我们让dp[0] = 0,dp[1] =1,从第2项开始，dp[i] = dp[i-1] + dp[i-2],从 2到 n遍历完成后，dp[n] 即得到了第n个斐波那契数，这就是这道题的动态规划思路
  

动态规划求解斐波那契数

public class DpTest2 {
    public static void main(String[] args) {
        for (int i = 10; i <= 40 ; i+= 10)
        {
            long start = System.currentTimeMillis();
            System.out.println(fibDpTest(i));
            long end = System.currentTimeMillis();
            System.out.println("动态规划求解第" + i + "个斐波那契数用时：" + (end -start) / 1000.0 + "s." );
        }
    }
    public static int fibDpTest(int n)
    {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        int len = n +1;
        int[] dp = new int[len];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i < len; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[len-1];
    }
}

本文链接：https://highphone.xyz/a3750514.html