动态规划解析以及简单demo

妖狐艹你老母 2023-02-21 06:18 13阅读 0赞

# **简介** #

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

# **基本思想** #

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

先看个简单的Demo 看下感觉

# **例题1：** #

假设你正在爬楼梯。需要 *n* 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

**注意：**给定 *n* 是一个正整数。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmd4dWVsZWkwMzY_size_16_color_FFFFFF_t_70][]

如何使用动态规划的思想解决呢？

我们用 dp\[i\]表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们知道第i层与第X-1与X-2有关系，也就是之前提到的阶段依赖问题，那么可以得出下面公式：

f(x) = f(x - 1) + f(x - 2)

它意味着爬到第 x 级台阶的方案数是爬到第 x - 1 级台阶的方案数和爬到第 x - 2级台阶的方案数的和。很好理解，因为每次只能爬 1级或 2 级，所以 f(x) 只能从 f(x−1) 和 f(x−2) 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。

以上是动态规划的转移方程，下面我们来讨论边界条件。我们是从第 00级开始爬的，所以从第 0级爬到第 0 级我们可以看作只有一种方案，即 f(0) = 1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1)=1。这两个作为边界条件就可以继续向后推导出第 nn 级的正确结果。我们不妨写几项来验证一下，根据转移方程得到 f(2)=2，f(3)=3，f(4)=5......我们把这些情况都枚举出来，发现计算的结果是正确的。

我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n)的实现，但是由于这里的f(x) 只和 f(x - 1)与 f(x - 2) 有关，所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)。

那么代码也很简单，这里就不去展示出来了，感兴趣的可以自己尝试写一写，就是累计阶段相加问题。  
题目来源链接：[https://leetcode-cn.com/problems/climbing-stairs/][https_leetcode-cn.com_problems_climbing-stairs]

不知道有没有什么感觉了，那么就带着感觉来看下动态规划基本的概念。

# **基本概念** #

**1. 多阶段决策问题**

如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策（采取措施），一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题 。

各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果

**2．动态规划问题中的术语**

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

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

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

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

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

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

知道概念了，可以回想下哪些概念在刚刚那个例子里面的哪些地方。

# **例子2：打家劫舍 （现实生活中我们可是良好市民）** #

那么再来一个Demo 再看下感觉，剩下的就只是去大量熟悉各种案例，就能熟能掌握了

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmd4dWVsZWkwMzY_size_16_color_FFFFFF_t_70 1][]

首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。

如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第k (k>2) 间房屋，有两个选项：

偷窃第 k 间房屋，那么就不能偷窃第 k-1 间房屋，偷窃总金额为前 k-2 间房屋的最高总金额与第 k 间房屋的金额之和。

不偷窃第 k 间房屋，偷窃总金额为前 k-1 间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。

在思考的时候，先要知道dp\[i\] 与 前面哪几个阶段有关，这里是和 i-1 与 i-2 阶段有关

用 dp\[i\] 表示前 i间房屋能偷窃到的最高总金额，那么就有如下的**状态转移方程**：

dp\[i\] = max\{dp\[i-2\] + nums\[i\] , dp\[i-1\]\}

边界条件为：

dp\[0\]=nums\[0\]                           只有一间房屋，则偷窃该房屋  
dp\[1\]=max(nums\[0\],nums\[1\])    只有两间房屋，选择其中金额较高的房屋进行偷窃

最终就可以得到最后的最大金额的dp\[i\]  也就是 数组长度-1

题目来源力扣:[https://leetcode-cn.com/problems/house-robber/][https_leetcode-cn.com_problems_house-robber]

代码如下:

class Solution {
        public int rob(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int length = nums.length;
            if (length == 1) {
                return nums[0];
            }
            int[] dp = new int[length];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0], nums[1]);
            for (int i = 2; i < length; i++) {
                dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
            }
            return dp[length - 1];
        }
    }

leetcode上面还有很多优秀的题目 大家可以去试试

[Link 1]: https://baike.baidu.com/item/%E6%9C%80%E4%BC%98%E5%80%BC
[Link 2]: https://baike.baidu.com/item/%E5%88%86%E6%B2%BB%E6%B3%95
[Link 3]: https://baike.baidu.com/item/%E8%BF%99%E4%BA%9B%E5%AD%90
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmd4dWVsZWkwMzY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200629100014710.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmd4dWVsZWkwMzY=,size_16,color_FFFFFF,t_70
[https_leetcode-cn.com_problems_climbing-stairs]: https://leetcode-cn.com/problems/climbing-stairs/
[Link 4]: https://baike.baidu.com/item/%E9%98%B6%E6%AE%B5
[Link 5]: https://baike.baidu.com/item/%E7%8A%B6%E6%80%81
[Link 6]: https://baike.baidu.com/item/%E6%97%A0%E5%90%8E%E6%95%88%E6%80%A7
[Link 7]: https://baike.baidu.com/item/%E5%86%B3%E7%AD%96
[Link 8]: https://baike.baidu.com/item/%E5%86%B3%E7%AD%96%E5%8F%98%E9%87%8F
[Link 9]: https://baike.baidu.com/item/%E7%AD%96%E7%95%A5
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmd4dWVsZWkwMzY_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200629101108560.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmd4dWVsZWkwMzY=,size_16,color_FFFFFF,t_70
[https_leetcode-cn.com_problems_house-robber]: https://leetcode-cn.com/problems/house-robber/