当前位置:网站首页>966 minimum path sum
966 minimum path sum
2022-07-06 21:00:00 【-Lin Zeyu】
The title is as follows
Given a... That contains a nonnegative integer m x n grid grid , Please find a path from the top left corner to the bottom right corner , Make the sum of the numbers on the path the smallest .
explain : You can only move down or right one step at a time .
Example 1:
Input :grid = [[1,3,1],[1,5,1],[4,2,1]]
Output :7
explain : Because the path 1→3→1→1→1 The sum of is the smallest .
Example 2:
Input :grid = [[1,2,3],[4,5,6]]
Output :12
m = = grid.length
n = = grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
Their thinking
Dynamic programming
Solution code
class Solution
{
public:
int minPathSum(vector<vector<int>>& grid)
{
int m = grid.size(), n = grid[0].size(), dp[m][n], i, j;
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
if (i == 0 && j == 0)
{
dp[0][0] = grid[0][0];
}
else if (i == 0 && j != 0)
{
dp[i][j] = dp[i][j - 1] + grid[i][j];
}
else if (j == 0 && i != 0)
{
dp[i][j] = dp[i - 1][j] + grid[i][j];
}
else
{
dp[i][j] = std::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
}
return dp[m - 1][n - 1];
}
};
边栏推荐
- [DSP] [Part 1] start DSP learning
- Yyds dry goods count re comb this of arrow function
- 动态切换数据源
- 硬件开发笔记(十): 硬件开发基本流程,制作一个USB转RS232的模块(九):创建CH340G/MAX232封装库sop-16并关联原理图元器件
- PHP saves session data to MySQL database
- (work record) March 11, 2020 to March 15, 2021
- (工作记录)2020年3月11日至2021年3月15日
- R language visualizes the relationship between more than two classification (category) variables, uses mosaic function in VCD package to create mosaic plots, and visualizes the relationship between tw
- What programming do children learn?
- 15 millions d'employés sont faciles à gérer et la base de données native du cloud gaussdb rend le Bureau des RH plus efficace
猜你喜欢
Deployment of external server area and dual machine hot standby of firewall Foundation
【mysql】触发器
Intel 48 core new Xeon run point exposure: unexpected results against AMD zen3 in 3D cache
Reference frame generation based on deep learning
2022 Guangdong Provincial Safety Officer C certificate third batch (full-time safety production management personnel) simulation examination and Guangdong Provincial Safety Officer C certificate third
None of the strongest kings in the monitoring industry!
Logic is a good thing
Common doubts about the introduction of APS by enterprises
What is the problem with the SQL group by statement
New database, multidimensional table platform inventory note, flowus, airtable, seatable, Vig table Vika, Feishu multidimensional table, heipayun, Zhixin information, YuQue
随机推荐
Spiral square PTA
正则表达式收集
自定义限流注解
C language operators
Tips for web development: skillfully use ThreadLocal to avoid layer by layer value transmission
数据湖(八):Iceberg数据存储格式
Deployment of external server area and dual machine hot standby of firewall Foundation
基于STM32单片机设计的红外测温仪(带人脸检测)
Comprehensive evaluation and recommendation of the most comprehensive knowledge base management tools in the whole network: flowus, baklib, jiandaoyun, ones wiki, pingcode, seed, mebox, Yifang cloud,
3D face reconstruction: from basic knowledge to recognition / reconstruction methods!
快过年了,心也懒了
Redis insert data garbled solution
Review questions of anatomy and physiology · VIII blood system
Summary of different configurations of PHP Xdebug 3 and xdebug2
[DSP] [Part 1] start DSP learning
【OpenCV 例程200篇】220.对图像进行马赛克处理
Pinduoduo lost the lawsuit, and the case of bargain price difference of 0.9% was sentenced; Wechat internal test, the same mobile phone number can register two account functions; 2022 fields Awards an
How to turn a multi digit number into a digital list
PG basics -- Logical Structure Management (transaction)
c#使用oracle存储过程获取结果集实例