动态规划问题-LeetCode 64、135（58同城笔试题）

2019 年 10 月 4 日
筆記

作者：TeddyZhang，公众号：算法工程师之路

DP基础问题：LeetCode #64 #135

编程题

【LeetCode #64】最小路径和

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

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

示例:

输入:

[ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。

解题思路：

这道题目也是一个经典的动态规划题目，首先题目中说明了：每次只能向下走或者向右移动一步，因此我们可以建立一个dp矩阵，大小为m行n列，其中dp[i][j]表示从左上角[0][0]位置到[i][j]位置的最小路径和。因此我们可以得到递推式为：

dp[i][j]=min(dp[i-1][j], dp[i][j-1])+grid[i][j]

注意i=0或者j=0时，即第一行或者第一列，数组会越界，因此需要进行判断。对于i=0的情况：dp[i][j]=dp[i][j-1]+grid[i][j], j=0的情况同理可得！当我们得到递推式以后，就可以很快的写出代码了，主要是注意不要越界就好了，并且由于我们代码循环中没有判断i,j同时为零的情况，因此需要对其进行初始化！

C++代码：

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

同时，我们可以将上面的代码进行优化处理，不使用额外的空间dp矩阵，而是将dp矩阵建立在原数据grid上，但我以为这样会改变原数据，工程中不可以，但优化空间还是OK的！

class Solution {  public:      int minPathSum(vector<vector<int>>& grid) {          int m = grid.size(), n = grid[].size();          for(int i = ; i < m;i++){              for(int j = ; j < n;j++){                  if(i ==  && j != ) grid[i][j] += grid[i][j-1];                  if(i !=  && j == ) grid[i][j] += grid[i-1][j];                  if(i * j != )                      grid[i][j] += min(grid[i][j-1], grid[i-1][j]);              }          }          return grid[m-1][n-1];      }  };

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-path-sum

【LeetCode #135】分发糖果

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。相邻的孩子中，评分高的孩子必须获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1: 输入: [1,0,2] 输出: 5 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。示例 2: 输入: [1,2,2] 输出: 4 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

解题思路：

首先我们对整个数组进行初始化为1，dp[n]中元素都为1，第一次从左向右进行遍历，如果右边的得分大于左边的得分，则右边分得的糖果数比坐边多一个，不能贪多哟！但是我们并没有更新左边得分大于右边得分的情况，因此需要第二次遍历！

第二次遍历从右向左，类似于第一次，当ratings[i]>ratings[i+1]的同时，还要满足dp[i]<=dp[i+1]，为什么要多一个条件呢？这是因为第一次遍历确定了部分糖果数的正确大小关系，第二次遍历不能更改，加上这个条件后，我们只更新第一次遍历错误的糖果数！

C++代码：时间复杂度O(2*n)=O(n)

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/candy

完