动态规划问题-LeetCode 64、135（58同城笔试题）
动态规划问题-LeetCode 64、135（58同城笔试题）
作者：TeddyZhang，公众号：算法工程师之路
DP基础问题：LeetCode #64 #135
1
编程题
【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
完
腾讯云开发者
