当前位置:网站首页>Sword finger offer II 099 Sum of minimum paths - double hundred code
Sword finger offer II 099 Sum of minimum paths - double hundred code
2022-07-02 23:04:00 【Mr Gao】
The finger of the sword Offer II 099. Sum of minimum paths
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 : A robot 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
The key to solving this problem is to know , Each point is obtained from the upper point or the left point
The solution code is as follows :
int minPathSum(int** grid, int gridSize, int* gridColSize){
int i,j;
int n=gridSize,m=gridColSize[0];
// printf("nm %d %d || ",n,m);
int k=fmin(m,n);
for(i=0;i<k;i++){
for(j=i;j<m;j++){
// printf("%d %d ",i,j);
if(j==0&&i==0){
continue;
}
if(i==0){
grid[i][j]=grid[i][j-1]+ grid[i][j];
}
else{
if(grid[i][j-1]<grid[i-1][j]){
grid[i][j]=grid[i][j]+grid[i][j-1];
}
else{
grid[i][j]=grid[i][j]+grid[i-1][j];
}
}
// printf("%d %d %d ",i,j,grid[i][j]);
}
for(j=i+1;j<n;j++){
if(i==0){
grid[j][i]=grid[j-1][i]+ grid[j][i];
}
else{
if(grid[j][i-1]<grid[j-1][i]){
grid[j][i]=grid[j][i]+grid[j][i-1];
}
else{
grid[j][i]=grid[j][i]+grid[j-1][i];
}
}
// printf("-%d %d %d " ,j,i,grid[j][i]);
}
}
return grid[n-1][m-1];
}
边栏推荐
- 2016. 增量元素之间的最大差值
- 数据标注典型案例,景联文科技如何助力企业搭建数据方案
- 剑指 Offer II 099. 最小路径之和-双百代码
- DTM distributed transaction manager PHP collaboration client V0.1 beta release!!!
- 景联文科技低价策略帮助AI企业降低模型训练成本
- 归并排序详解及应用
- MySQL查询附近的数据.并按距离进行排序.
- PMP project integration management
- Chow-Liu Tree
- Tronapi-波场接口-源码无加密-可二开--附接口文档-基于ThinkPHP5封装-作者详细指导-2022年7月1日08:43:06
猜你喜欢
boot actuator - prometheus使用
从2022年Q1财报看携程的韧性和远景
Go语言sqlx库操作SQLite3数据库增删改查
Niuke network: maximum submatrix
[chestnut sugar GIS] ArcMap - why should the tick of classic capture be removed when using custom capture?
[npuctf2020]ezlogin XPath injection
【硬件】标准阻值的由来
中国信通院、清华大学、腾讯安全,云原生安全产学研用强强联合!
P1007 single log bridge
Lambda expression: an article takes you through
随机推荐
The first batch of Tencent cloud completed the first cloud native security maturity assessment in China
解决Chrome浏览器和Edeg浏览器主页被篡改的方法
Construction of Hisilicon 3559 universal platform: rotation operation on the captured YUV image
STM32之ADC
分享 10 个 JS 闭包面试题(图解),进来看看你能答对多少
DTM distributed transaction manager PHP collaboration client V0.1 beta release!!!
1px pixel compatibility of mobile terminal, 1px border
Golang's learning route
分布式监控系统zabbix
数据分析学习记录(二)---响应曲面法及Design-Expert的简单使用
[Yangcheng cup 2020] easyphp
归并排序详解及应用
Value sequence < detailed explanation of daily question >
创新实力再获认可!腾讯安全MSS获2022年度云原生安全守护先锋
Pytorch training CPU usage continues to grow (Bug)
Higher order operation of bits
Qt QScrollArea
Successfully changed Splunk default URL root path
首批 | 腾讯云完成国内首个云原生安全成熟度评估
E-commerce system microservice architecture