算法之动态规划1.0_vlambda技术博客

vlambda
2022-04-09

算法之动态规划1.0

“ 《数据结构与算法--从入门到放弃》学习笔记。”

先来一点基础一点的动态规划学习（同步进行一些深度优先搜索和广度优先搜索）。学习dp不是很深入，所以只是梳理一下思想。坚持写算法的第 9 天。（题源皆来自leetcode捏）

—

70.爬楼梯

先来康康题目：

分析一下题目，每次跨越一次台阶，我们可能跨越一步，也可能跨越两步，那么对于 3 阶台阶，我们可能从第一个台阶跨越到第三个台阶，也可能从第二个台阶跨越，那么 3 阶台阶的跨越方法就是前两个跨越台阶方法的和，推到 n 阶台阶也就是斐波那契数列。

斐波那契数列熟悉的可能是递归方法，类似于二叉树，但会由于重复计算导致额外的时间花费。对其进行一个剪枝操作，即用一个备忘录(dp table)去记录每个 n 对应的值(状态)，进行一个自低向上的运算。所以这里确定状态是每一阶爬楼梯的方法数。那么很容易就能得到dp[i] = dp[i - 1] + dp[i - 2]。

康康题解：

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

—

198.打家劫舍

康康第二题：

算法之动态规划1.0

分析一下题目，什么叫专业的小偷啊？打工是不可能打工的，抢劫还要分析怎么抢，结果一看偷一晚上连一伯块都偷不到。接下来是正经分析，看到这种需要记录偷的钱的总量，如果有更好的选择就换的一般都使用动态规划（贪心也会有一部分）。那么对于行窃过程，我们假设这个专业的小偷经过i这个房屋，那么就有两种选择，偷还是不偷（这不是废话吗？）。如果偷的话，那上一个房屋一定不偷（直接推，dp[i] = di[i - 2] + nums[i]），如果不偷，那直接推，这个状态和上一个状态相同（dp[i] = dp[i - 1]）。但是这是状态和数组同步进行的情况，也就是 dp[i] 对应nums[i] 的情况，但这样要额外考虑 n == 1 || 2 的情况。那么我们给 dp在加上一种最初始状态0，那么就不需要额外再考虑上述情况了，对应的dp[i] = di[i - 2] + nums[i - 1]。

附上答案：

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

—

64.最小路径和

仔细阅读下题目：

分析一下，我们只要设置一个相同大小的二维数组dp作为所需走的最短步数记录就行。怎么比较最短就是这个二维数组中的值去比较左边和上面的值，因为移动的时候每次只能向下或者向右移动一步。那么我们还需要处理的情况是没有左边值和上边值得情况，最后这个二维数组dp得最后一个值就是我们要求得结果。

康康代码：

class Solution {public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); vector<vector<int>> dp(m, vector(n, 0)); for(int i = 0; i < m; i++) for(int j = 0; j < n; j++){ 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 - 1][j], dp[i][j - 1]) +grid[i][j]; } return dp[m - 1][n - 1]; }};