【算法】动态规划

概念引入

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法

思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式

术语

• 阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。

• 状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。

• 无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性
  。

• 决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多问题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。

• 决策变量的范围称为允许决策集合。

• 策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。

  允许策略集合中达到最优效果的策略称为最优策略 。
  给定k阶段状态变量x(k)的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么可以把这一关系看成(x(k)，u(k))与x(k+1)确定的对应关系，用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律，称为状态转移方程 。

• 最优化原理：作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略” 。

  最优性原理实际上是要求问题的最优策略的子策略也是最优

要应用动态规划，问题就必须具备以下两个属性：

• 最优子结构（Optimal substructure）
• 重叠子问题（Overlapping subproblems）

（1）最优子结构

如果大小为n的问题的最优解可以由大小小于n的问题的同一实例的最优解推导出，则该问题具有最优子结构。

例如，如果从巴黎到莫斯科的最短路径会经过柏林，那么可以由巴黎到柏林的最短路径和柏林到莫斯科的最短路径组成。

如果一个问题可以通过组合非重叠子问题的最优解来解决，这种策略被称为分治法。这就是归并排序和快速排序不属于动态规划问题的原因。

（2）重叠子问题

举一个大家都很熟悉的例子，斐波那契数列，即从第三项开始，每一项都等于前两项之和。斐波那契数列可以表示为

F(0) = F(1) = 1F(n) = F(n-1) + F(n-2)

大家都说一张图片胜过千言万语，所以…（摘自《Elements of programming interviews》）

要想解出F（n），就需要解出F（n-1）和F（n-2），但是F（n-1）又需要F（n-2）和F（n-3）。这样一来，F（n-2）是重复的，来自于同一个问题的两个不同实例——计算一个斐波那契数。

这可以用一个递归函数来表示：

要想解决一个大小为n的问题，我们可以调用相同的函数来解决同一问题的一个实例，但实例规模比原始问题规模小一些。
我们一直不断地调用该函数，直到到达基础用例，也就是停止条件，在此处即n = 0或n = 1。
这就引出了递归和动态规划之间的关系。

递归和动态规划

从概念上讲，动态规划涉及到递归问题。我们希望通过同一个问题的较小实例来解决原始问题，而递归是在代码中实现这一点的最佳选择。与纯递归函数的不同之处在于，我们将用空间来换取时间：我们将存储各子问题的最优解，进而高效地找到原始问题的最优解。

当然，这并不是说我们都必须使用递归来解决动态规划问题。还可以通过一种迭代方法来编写动态规划解决方案。

斐波那契数列

斐波那契数列：F1=Fn-1+Fn-2

分别用递归和非递归实现一下
递归

    //递归
    public int FibnacciA(int n)
    {
        int res;
        if (n == 1 || n == 2)
            res = 1;
        else
            res = (FibnacciA(n - 1) + FibnacciA(n - 2));
        return res;
    }
1
2
3
4
5
6
7
8
9
10

非递归

    //非递归
    public int FibnacciB(int n)
    {
        List<int> f = new List<int>() { 0, 1, 1 };//斐波那契数列先初始化前3个特殊的
        if (n>2)
        {
            //n=3 计算1次 n=5 计算3次
            for (int i = 0; i < n-2; i++)
            {
                int fl= f.Count;
                f.Add(f[fl - 1] + f[fl - 2]);
            }
        }
        return f[n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

经过测试都是对的，但是重点不是这个，重点是运行时间

很明显非递归快的多，而且递归50或者100的时候，我直接卡死了。为啥

因为递归方法里有很多子问题的重复计算，而且数字越大，子问题重复越严重

而非递归的方法里子问题不会重复，而是存起来了

那么非递归的那个方法就可以称为动态规划（DP）

能够动态规划的问题需要两个关键点 1有递推式 2有重复子问题

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。
示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

方法：动态规划

由于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。

对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，因此可以使用动态规划求解。

创建二维数组 dp，与原始网格的大小相同，dp[i][j] 表示从左上角出发到 (i,j)(i,j) 位置的最小路径和。显然，dp[0][0]=grid[0][0]。对于 dp 中的其余元素，通过以下状态转移方程计算元素值。

• 当 i>0且 j=0时，dp[i][0]=dp[i−1][0]+grid[i][0]。
• 当 i=0且 j>0时，dp[0][j]=dp[0][j−1]+grid[0][j]。
• 当 i>0且 j>0时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]。

最后得到 dp[m−1][n−1] 的值即为从网格左上角到网格右下角的最小路径和。

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, columns = grid[0].length;
        int[][] dp = new int[rows][columns];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

来源

百度百科
关于动态规划，你想知道的都在这里了
动态规划_C#
力扣-最小路径和