动态规划的详细介绍及其相关LeetCode例题

2023-04-01 10:54| 来源: 网络整理| 查看: 265

本文目录 1. 什么是动态规划(Nynamic Programming，简称DP)2. 动态规划中的常见概念3. 动态规划问题的解题步骤4. 动态规划的性质5. 学习动态规划的一些建议6. LeetCode中典型的动态规划的例题70. 爬楼梯（easy）198. 打家劫舍（med）509. 斐波那契数（easy）413. 等差数列划分（med）64. 最小路径和（med）47. 礼物的最大价值（med）

1. 什么是动态规划(Nynamic Programming，简称DP) 动态规划是一种用于解决一些优化问题的算法。这些问题通常是在多个阶段中逐步解决，每个阶段都要做出一些决策，每个决策可能会对后续阶段产生影响。动态规划的目标是在给定限制条件下找到最优的决策，以最大化或最小化某个预定义变量的值。通常情况下，动态规划涉及到一个尝试在某种限制条件下找到最优解的问题。解决这种问题的一种方法是将问题分解成较小的子问题，并使用这些子问题的最优解构建出整个问题的最优解。这个过程通常是通过一个计算表格来完成的，并且可以使用缓存来避免重复的计算。动态规划可以应用于广泛的问题领域，例如序列比对，背包问题，图形优化等等。该算法的实现通常可以采用自底向上的方式来避免嵌套循环的噪声和递归的开销。它也可以在一些特定条件下应用于无序的序列数据，例如最长递增子序列问题。 2. 动态规划中的常见概念子问题和原问题：原问题就是你要求解的这个问题本身，子问题是和原问题相似但规模较小的问题（原问题本身就是子问题的最复杂的情形，即子问题的特例）。例如：要求F(10)，那么求出F(10)就是原问题，求出F(k)(kB->C （1）状态A确定后不会再受到B和C状态决策的影响，只和状态A之前的状态有关；（2）状态B的确定是由状态A转化而来，B状态确定后不再受C状态的影响；（3）状态C确定是由状态A和B转化而来。无后效性的另一种重要的定义：无后效性是指如果在某个阶段上过程的状态已知，则从此阶段以后过程的发展变化仅与此阶段的状态有关，而与过程在此阶段以前的阶段所经历过的状态无关。举例：依然用上面的A，B，C三个状态举例：（1）状态A确定后，可以转化为状态B；（2）状态B确定后，状态C可以由状态B转化而来，但是“状态C和状态A无关！只是由状态B转化而来的”。有重叠子问题：即子问题之间是不独立的（分治法是独立的），一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势） 5. 学习动态规划的一些建议

动态规划是一种常用的算法设计和优化技术，它通常用于求解具有优化子结构的问题。下面是一些学习和理解动态规划的建议：

了解动态规划的基本思想和应用场景。动态规划的基本思想是通过将复杂问题拆分成简单的子问题来解决原问题。它通常用于解决具有重叠子问题和最优子结构的问题，并在求解过程中利用已经解决的子问题的解来加快求解过程。实践编写动态规划的代码。动态规划的关键在于设计状态转移方程和状态转移顺序，因此需要不断练习编写动态规划的代码来加深理解和熟练掌握动态规划的基本技巧。可以从一些简单的问题入手，例如斐波那契数列、背包问题等。学习常见的动态规划算法。掌握动态规划算法的常见思路和方法可以帮助我们更好地解决各种问题。例如，最长公共子序列、最长上升子序列、背包问题、编辑距离等。阅读相关教材和学习视频。动态规划是一种较为抽象和高级的算法技术，因此需要阅读相关的书籍和教材。例如《算法竞赛入门经典》、《算法导论》等。参加比赛和做题练习。参加算法竞赛或完成相关问题的练习可以帮助我们更好地理解动态规划，并提升算法分析和实现能力。

最后，需要注意的是，动态规划虽然是一种常用的算法技术，但它并不是所有问题的最优解，有些问题也可能有其他更好的解法。因此，在解决问题时应按照实际情况选择适合的算法方法。

6. LeetCode中典型的动态规划的例题 70. 爬楼梯（easy）

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

示例 1：

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

示例 2：

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

第一版：动态规划，时间0ms，击败100%；空间6.1MB，击败20.19%。

class Solution { public: int climbStairs(int n) { if(n dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } };

思路：这是十分经典的斐波那契数列题。定义一个数组 dp，dp[i] 表示走到第 i 阶的方法数。因为我们每次可以走一步或者两步，所以第 i 阶可以从第 i-1 或 i-2 阶到达。换句话说，走到第 i 阶的方法数即为走到第 i-1 阶的方法数加上走到第 i-2 阶的方法数。这样我们就得到了状态转移方程dp[i] = dp[i-1] + dp[i-2]。注意边界条件的处理。

第二版：动态规划（滑动数组），时间0ms，击败100%；空间5.7MB，击败97.8%。

class Solution { public: int climbStairs(int n) { if (n public: int rob(vector& nums) { if(nums.empty()) { return 0; } int size = nums.size(); if(size == 1) { return nums[0]; } vector dp = vector(size, 0); dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for (int i = 2; i public: int rob(vector& nums) { if (nums.empty()) return 0; int n = nums.size(); if (n == 1) return nums[0]; int pre2 = 0, pre1 = 0, cur; for (int i = 0; i public: int fib(int n) { return n if(n == 0) { return 0; } if(n == 1) { return 1; } vectornums(n + 1, 0); nums[1] = 1; for(int i = 2; i public: int fib(int n) { if(n p = q; q = r; r = p + q; } return r; } };

解释：斐波那契数的边界条件是 F(0)=0 和 F(1)=1 。当 n>1 时，每一项的和都等于前两项的和，因此有如下递推关系：F(n)=F(n−1)+F(n−2)。由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0) 和 F(1) 。

根据状态转移方程和边界条件，可以得到时间复杂度和空间复杂度都是 O(n) 的实现。由于 F(n) 只和 F(n−1) 与 F(n−2) 有关，因此可以使用「滚动数组思想」把空间复杂度优化成 O(1) 。

413. 等差数列划分（med）

题目描述：点我直击原题如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的子数组个数。子数组是数组中的一个连续序列。

示例 1：

输入：nums = [1,2,3,4] 输出：3 解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例 2：

输入：nums = [1] 输出：0

第一版：动态规划。时间0ms，击败100%；空间7.3MB，击败6.6%。

class Solution { public: int numberOfArithmeticSlices(vector& nums) { int n = nums.size(); if(n dp[i] = dp[i - 1] + 1; } } return accumulate(dp.begin(), dp.end(), 0); } };

思路：这道题略微特殊，因为要求是等差数列，可以很自然的想到子数组必定满足num[i] - num[i-1] = num[i-1] - num[i-2]。然而由于我们对于 dp 数组的定义通常为以 i 结尾的，满足某些条件的子数组数量，而等差子数组可以在任意一个位置终结，因此此题在最后需要对 dp 数组求和。

64. 最小路径和（med）

题目描述：点我直击原题给定一个包含非负整数的 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

第一版：动态规划（二维）。时间12ms，击败29.92%；空间9.8MB，击败42.31%。

class Solution { public: int minPathSum(vector& grid) { int m = grid.size(), n = grid[0].size(); vectordp(m, vector(n, 0)); for(int i = 0; i if(i == 0 && j == 0) { dp[i][j] = grid[i][j]; } else if(i == 0) { dp[i][j] = dp[i][j - 1] + grid[i][j]; } else if(j == 0) { dp[i][j] = dp[i - 1][j] + grid[i][j]; } else { dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]; } } } return dp[m - 1][n - 1]; } };

思路：我们可以定义一个同样是二维的 dp 数组，其中dp[i][j]表示从左上角开始到 (i, j) 位置的最优路径的数字和。因为每次只能向下或者向右移动，我们可以很容易得到状态转移方程dp[i][j] =min(dp[i-1][j], dp[i][j-1]) + grid[i][j]，其中 grid 表示原数组。

第二版：动态规划（压缩空间）。时间4ms，击败98.3%；空间9.3MB，击败92.85%。

class Solution { public: int minPathSum(vector& grid) { int m = grid.size(), n = grid[0].size(); vectordp(n, 0); for(int i = 0; i if(i == 0 && j == 0) { dp[j] = grid[i][j]; } else if(i == 0) { dp[j] = dp[j - 1] + grid[i][j]; } else if(j == 0) { dp[j] = dp[j] + grid[i][j]; } else { dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]; } } } return dp[n - 1]; } };

思路：因为 dp 矩阵的每一个值只和左边和上面的值相关，我们可以使用空间压缩将 dp 数组压缩为一维。对于第 i 行，在遍历到第 j 列的时候，因为第 j-1 列已经更新过了，所以dp[j-1]代表dp[i][j-1]的值；而dp[j]待更新，当前存储的值是在第 i-1 行的时候计算的，所以代表dp[i-1][j]的值。

温馨提示：理解这道题后，可以拿下面这道题练手！

47. 礼物的最大价值（med）

题目描述：点我直击原题在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

输入： [ [1,3,1], [1,5,1], [4,2,1] ] 输出：12 解释：路径 1→3→5→2→1 可以拿到最多价值的礼物

第一版：动态规划（二维）。时间4ms，击败96.58%；空间9.3MB，击败7.22%。

class Solution { public: int minPathSum(vector& grid) { int m = grid.size(), n = grid[0].size(); vectordp(m, vector(n, 0)); for(int i = 0; i if(i == 0 && j == 0) { dp[i][j] = grid[i][j]; } else if(i == 0) { dp[i][j] = dp[i][j - 1] + grid[i][j]; } else if(j == 0) { dp[i][j] = dp[i - 1][j] + grid[i][j]; } else { dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]; } } } return dp[m - 1][n - 1]; } };

第二版：动态规划（压缩空间）。时间4ms，击败96.58%；空间8.8MB，击败84.51%。

class Solution { public: int maxValue(vector& grid) { int m = grid.size(), n = grid[0].size(); vectordp(n, 0); for(int i = 0; i if(i == 0 && j == 0) { dp[j] = grid[i][j]; } else if(i == 0) { dp[j] = dp[j - 1] + grid[i][j]; } else if(j == 0) { dp[j] = dp[j] + grid[i][j]; } else { dp[j] = max(dp[j], dp[j - 1]) + grid[i][j]; } } } return dp[n - 1]; } };

【本文地址】

公司简介

联系我们