动态规划入门

• 前言
• 一、动态规划是什么？
• 二、动态规划的核心思想
• 三、经典例题
• • 1.斐波那契数
  • 2.第 N 个泰波那契数
  • 3. 爬楼梯
  • 4. 打家劫舍
  • 5.打家劫舍 II
  • 6.删除并获得点数
  • 7.跳跃游戏
  • 8.跳跃游戏 II
  • 9.最大子数组和
  • 10.环形子数组的最大和
  • 11. 乘积最大子数组
  • 12.乘积为正数的最长子数组长度
• 总结

前言

我们在刷算法题的时候，经常会遇到动态规划类型题目。动态规划问题非常非常多，今天跟大家一起来学习动态规划的套路，文章如果有不正确的地方，欢迎指出。

一、动态规划是什么？

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等地方，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

二、动态规划的核心思想

动态规划最核心的思想，就在于拆分子问题，得到关系转化式，减少重复计算。

三、经典例题

1.斐波那契数

leetcode原题链接

题目描述：
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。 (0 <= n <= 30)

• 通过题目描述可以得到转化方程为 F(n) = F(n - 1) + F(n - 2）根据转化关系我们就可以求出任一项的值具体是多少，代码如下：

class Solution {public:    int fib(int n) { int f[35];//题目限制范围是0-30，所以多申请一点空间避免溢出 f[1] = f[2] = 1; //前两位数都是1，可以简写，等价于f[1] = 1; f[2] = 1; if (n == 0)return 0; if (n == 1 || n == 2)return 1; for (int i = 3; i <= n; i++)     f[i] = f[i - 1] + f[i - 2];//转化关系 return f[n];    }};

• 纯净无注释版

class Solution {public:    int fib(int n) { int f[35]; f[1] = f[2] = 1; if (n == 0)return 0; if (n == 1 || n == 2)return 1; for (int i = 3; i <= n; i++)     f[i] = f[i - 1] + f[i - 2]; return f[n];    }};

2.第 N 个泰波那契数

leetcode原题链接

题目描述：
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。（0 <= n <= 37）

• 由题意可知转化方程为 Tn+3 = Tn + Tn+1 + Tn+2 即任意一个数等于前面三个数的和，代码如下：

class Solution {public:    int tribonacci(int n) { int f[40];//数据范围是0-37所以申请40个空间 f[0] = 0; f[1] = 1; f[2] = 1;//前三个数的默认值 for (int i = 3; i <= n; i++)     f[i] = f[i - 1] + f[i - 2] + f[i - 3];//转化关系 return f[n];    }};

• 纯净无注释版

class Solution {public:    int tribonacci(int n) { int f[40]; f[0] = 0; f[1] = 1; f[2] = 1; for (int i = 3; i <= n; i++)     f[i] = f[i - 1] + f[i - 2] + f[i - 3]; return f[n];    }};

3. 爬楼梯

leetcode原题链接

题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
(1 <= n <= 45)

示例1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
(1)1 阶 + 1 阶
(2)2 阶

示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
(1)1 阶 + 1 阶 + 1 阶
(2)1 阶 + 2 阶
(3)2 阶 + 1 阶

• 题目分析：
  假设有1个台阶，只有1种方法
  假设有2级台阶，只有2种方法
  假设有3级台阶
  先爬1阶，接下来还有2阶台阶，那问题就是有2阶台阶怎么爬
  先爬2阶，接下来还有1阶台阶，那问题就是有1阶台阶怎么爬
  好像有规律的，再往下分析分析
  假设有4级台阶
  先爬1阶，接下来还有3阶台阶，那问题就是有3阶台阶怎么爬
  先爬2阶，接下来还有2阶台阶，那问题就是有2阶台阶怎么爬
  …
  假设有n级台阶
  先爬1阶，接下来还有 n - 1 阶台阶，那问题就是有n - 1阶台阶怎么爬
  先爬2阶，接下来还有 n - 2 阶台阶，那问题就是有n - 2阶台阶怎么爬

• 数学归纳法得出，有n阶台阶那么就是 n - 1 阶台阶和 n - 2 阶台阶爬上楼顶的方法的和。

• 公式： f(n) = f(n - 1) + f(n - 2) , 这不就是斐波那契数列数量求和吗？代码如下：

class Solution {public:    int climbStairs(int n) { int f[50];//数据范围是1-45 f[1] = 1; f[2] = 2; for (int i = 3; i <= n; i++)     f[i] = f[i - 1] + f[i - 2]; return f[n];    }};

4. 打家劫舍

leetcode原题链接

题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
1 <= nums.length <= 100
0 <= nums[i] <= 400

示例1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

• 题目分析：

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

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

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

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

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

用 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[n−1]，其中 n 是数组的长度。

class Solution {public:    int rob(vector<int>& nums) { if (nums.empty()) return 0;//如果nums为空，即没有房间可偷，返回0 int size = nums.size();//计算共有多少房间 if (size == 1) return nums[0];//若只有一间房则直接偷 int dp[110];//房间个数范围是0-100 dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for (int i = 2; i < size; i++)     dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);//状态转移方程      return dp[size - 1];    }};

• 纯净无注释版

class Solution {public:    int rob(vector<int>& nums) { if (nums.empty()) return 0; int size = nums.size(); if (size == 1) return nums[0]; int dp[110]; dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for (int i = 2; i < size; i++)     dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);      return dp[size - 1];    }};

5.打家劫舍 II

leetcode原题链接

题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
1 <= nums.length <= 100
0 <= nums[i] <= 1000

示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

• 题目分析：

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

注意到当房屋数量不超过两间时，最多只能偷窃一间房屋，因此不需要考虑首尾相连的问题。如果房屋数量大于两间，就必须考虑首尾相连的问题，第一间房屋和最后一间房屋不能同时偷窃。

如何才能保证第一间房屋和最后一间房屋不同时偷窃呢？如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。

假设数组 nums 的长度为 n。如果不偷窃最后一间房屋，则偷窃房屋的下标范围是 [0,n−2] 如果不偷窃第一间房屋，则偷窃房屋的下标范围是 [1,n−1]。在确定偷窃房屋的下标范围之后，即可用上题的方法解决。对于两段下标范围分别计算可以偷窃到的最高总金额，其中的最大值即为在 n 间房屋中可以偷窃到的最高总金额。

假设偷窃房屋的下标范围是 [start,end]，用 dp[i] 表示在下标范围 [start,i] 内可以偷窃到的最高总金额，那么就有如下的状态转移方程：

dp[i]=max(dp[i−2]+nums[i],dp[i−1])

边界条件为：
dp[start]=nums[start] 只有一间房屋，则偷窃该房屋
dp[start+1]=max(nums[start],nums[start+1]) 只有两间房屋，偷窃其中金额较高的房屋

计算得到 dp[end] 即为下标范围 [start,end] 内可以偷窃到的最高总金额。

分别取 (start,end) = (0,n−2) 和 (start,end) = (1,n−1) 进行计算，取两个 dp[end] 中的最大值，即可得到最终结果。

class Solution {public://求(start,end)的最大值,和上题操作完全一致    int robRange(vector<int>& nums, int start, int end) { int dp[110];//数据范围是0-100，dp[i]表示(start,i)的最大值 dp[start] = nums[start]; dp[start + 1] = max(nums[start], nums[start + 1]); for (int i = start + 2; i <= end; i++)     dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);//状态转化方程 return dp[end];    }    int rob(vector<int>& nums) { int length = nums.size();//求房间数量 if (length == 1) return nums[0];//只有一间房直接返回 else if (length == 2) return max(nums[0], nums[1]);//两间房返回其中较大的值 else return max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1)); //返回(0,n-2)与(1,n-1)的最大值    }};

• 纯净无注释版

class Solution {public:    int robRange(vector<int>& nums, int start, int end) { int dp[110]; dp[start] = nums[start]; dp[start + 1] = max(nums[start], nums[start + 1]); for (int i = start + 2; i <= end; i++)     dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]); return dp[end];    }    int rob(vector<int>& nums) { int length = nums.size(); if (length == 1) return nums[0]; else if (length == 2) return max(nums[0], nums[1]); else return max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));    }};

6.删除并获得点数

leetcode原题链接

题目描述：
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104

示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

• 题目分析：
  首先，我们先明确一个概念，就是每个位置上的数字是可以在两种前结果之上进行选择的：
  如果你不删除当前位置的数字，那么你得到就是前一个数字的位置的最优结果。
  如果你觉得当前的位置数字i需要被删，那么你就会得到i - 2位置的那个最优结果加上当前位置的数字乘以个数。
  以上两个结果，你每次取最大的，记录下来，然后答案就是最后那个数字了。
  如果你看到现在有点迷糊，那么我们先把数字进行整理一下。
  我们在原来的 nums 的基础上构造一个临时的数组 all，这个数组，以元素的值来做下标，下标对应的元素是原来的元素的个数。

举个例子：
nums = [2, 2, 3, 3, 3, 4]
构造后：
all=[0, 0, 2, 3, 1]; //0个0，0个1，2个2，3个3，1个4

• 我们来看看，打家劫舍的最优子结构的公式：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
  再来看看现在对这个问题的最优子结构公式：dp[i] = max(dp[i - 1], dp[i - 2] + i * all[i]);

class Solution {public:    int deleteAndEarn(vector<int>& nums) { if(nums.size() < 1) return 0; int n = 0; for(int item : nums) n = max(n, item);//求出nums中最大的数 vector<int> all(n+1), dp(n+1);//all保存nums中每个数的数量，dp表示能够获得的最大点数 for(int item : nums) all[item]++;//遍历一遍nums将每个数存到对应的all数组中 dp[1] = all[1]; for(int i = 2; i <= n; i++)     dp[i] = max(dp[i-1], dp[i-2] + all[i] * i);//状态转换公式 return dp[n];    }};

• 纯净无注释版

class Solution {public:    int deleteAndEarn(vector<int>& nums) { if(nums.size() < 1) return 0; int n = 0; for(int item : nums) n = max(n, item); vector<int> all(n+1), dp(n+1); for(int item : nums) all[item]++; dp[1] = all[1]; for(int i = 2; i <= n; i++)     dp[i] = max(dp[i-1], dp[i-2] + all[i] * i); return dp[n];    }};

• 不懂上面for循环用法的可以看这篇文章C++特性循环–foreach的用法详解——for ( i : n)

7.跳跃游戏

leetcode原题链接

题目描述：
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105

示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

• 题目分析：

我们可以用贪心的方法解决这个问题。
设想一下，对于数组中的任意一个位置 y，我们如何判断它是否可以到达？根据题目的描述，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x+nums[x]，这个值大于等于 y，即 x+nums[x]≥y，那么位置 y 也可以到达。

换句话说，对于每一个可以到达的位置 x，它使得 x+1,x+2,⋯,x+nums[x] 这些连续的位置都可以到达。

这样以来，我们依次遍历数组中的每一个位置，并实时维护 最远可以到达的位置。对于当前遍历到的位置 x，如果它在 最远可以到达的位置 的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x+nums[x] 更新 最远可以到达的位置。

在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

以题目中的示例一 [2, 3, 1, 1, 4] 为例：

我们一开始在位置 0，可以跳跃的最大长度为 2，因此最远可以到达的位置被更新为 2；

我们遍历到位置 1，由于 1≤2，因此位置 1 可达。我们用 1 加上它可以跳跃的最大长度 3，将最远可以到达的位置更新为 4。由于 4 大于等于最后一个位置 4，因此我们直接返回 True。

class Solution {public:    bool canJump(vector<int>& nums) { int n = nums.size();//数组长度 int x = 0;//x表示能够到达的最远位置 for (int i = 0; i < n; i++) {     if (i <= x)x = max(x, i + nums[i]);//对最远位置更新     if (x >= n - 1)return true;//如果能够到达的位置超过或等于最后一个坐标则返回true } return false;//无法到达最后一个坐标    }};

• 纯净无注释版

class Solution {public:    bool canJump(vector<int>& nums) { int n = nums.size(); int x = 0; for (int i = 0; i < n; i++) {     if (i <= x)x = max(x, i + nums[i]);     if (x >= n - 1)return true; } return false;    }};

8.跳跃游戏 II

leetcode原题链接

题目描述：
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
1 <= nums.length <= 104
0 <= nums[i] <= 1000

示例 :
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

• 题目分析：

如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点。 可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新。

如果从这个 起跳点 起跳叫做第 1 次 跳跃，那么从后面 3 个格子起跳 都 可以叫做第 2 次 跳跃。

所以，当一次 跳跃 结束时，从下一个格子开始，到现在 能跳到最远的距离，都 是下一次 跳跃 的 起跳点。
对每一次 跳跃 用 for 循环来模拟。 跳完一次之后，更新下一次 起跳点 的范围。 在新的范围内跳，更新 能跳到最远的距离。记录 跳跃 次数，如果跳到了终点，就得到了结果。

int jump(vector<int>& nums){    int ans = 0;//步数    int end = 0;//第ans次跳跃所达到的最远距离    int maxPos = 0;//当前可达到的最远距离    for (int i = 0; i < nums.size() - 1; i++)    { maxPos = max(nums[i] + i, maxPos);//更新最远距离 if (i == end)//如果走到第ans次跳跃所达到的最远距离，则步数加一，最远距离更新为当前可达到的最远距离 {     end = maxPos;     ans++; }    }    return ans;}

• 纯净无注释版

int jump(vector<int>& nums){    int ans = 0;    int end = 0;    int maxPos = 0;    for (int i = 0; i < nums.size() - 1; i++)    { maxPos = max(nums[i] + i, maxPos); if (i == end) {     end = maxPos;     ans++; }    }    return ans;}

9.最大子数组和

leetcode原题链接

题目描述：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
1 <= nums.length <= 105
-104 <= nums[i] <= 104

10.环形子数组的最大和

leetcode原题链接

题目描述：
给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], …, nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104​​​​​​​

11. 乘积最大子数组

leetcode原题链接

题目描述：
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

12.乘积为正数的最长子数组长度

leetcode原题链接

题目描述：
给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

总结

动态规划对于解决多阶段决策问题的效果是明显的，但是动态规划也有一定的局限性。首先，它没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理；另外当变量的维数增大时，总的计算量及存贮量急剧增大。因而，受计算机的存贮量及计算速度的限制，当今的计算机仍不能用动态规划方法来解决较大规模的问题，这就是“维数障碍”。

• 后续题目会持续更新，想要学习动态规划的小伙伴们可以先收藏关注，以便后续的学习。