首页 > Minimum Path Sum

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

 

格子取数问题,另dp[i][j]表示走到(i,j)格子时,取得的最小数字,那么有

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

当i=0时,只能从左边过来,当j=0时,只能从上面过来

 1 class Solution {
 2 public:
 3     int minPathSum(vectorint> > &grid) {
 4         int m = grid.size();
 5         int n = grid[0].size();
 6         if( m<0 || n<0 ) return 0;
 7         vector< vector<int> > dp(grid);
 8         for(int i=1; i0][i] += dp[0][i-1];
 9         for(int i=1; i0] += dp[i-1][0];
10         for(int i=1; ii)
11             for(int j=1; jj)
12                 dp[i][j] += min(dp[i-1][j], dp[i][j-1]);
13         return dp[m-1][n-1];
14     }
15 };

 

转载于:https://www.cnblogs.com/bugfly/p/4008593.html

更多相关:

  • 题目:正则表达式匹配 请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但与"aa.a"和"ab*a"均不匹配。 示例 1:...

  • 题意:就是在n*m的格子中放“炮”(中国象棋中的棋子)问有多少种放法,使得没有任意的两个炮相互攻击 思路:我们很容易的得到一列或者一行中最多放下两个炮(我也只能得到这些了,满脑子状压,但数据范围有100),这篇博客些的很好(传送门),我们定义dp[i][j][k]代表前i行我们有j列式有2个棋子,有k列是一个棋子,那么我们空的列的个数...

  • 虽然也是一道dp的入门题,但就是想不到,或者说不会实现。dp还是要多做题。 链接:https://www.luogu.org/problemnew/show/P1164   我们可以设dp[i][j]表示以考虑完第i件,恰好消费j元的方案数。那么dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]],也就是讨论第i件点...

  • bzoj1260,懒得复制,戳我戳我 Solution: 这种题目我不会做qwq,太菜了区间打牌(dp) 用f[l][r]表示从l到r最少需要染几次色。状态转移方程: 1.(f[l][r]=min(f[l][i],f[i+1][r]) (l<=i

  • 题目背景 博弈正在机房颓一个叫做《模拟城市2.0》的游戏。 2048年,经过不懈努力,博弈终于被组织委以重任,成为D市市委书记!他勤学好问,励精图治,很快把D市建设成富强民主文明和谐的美好城市。为了进一步深化发展,他决定在海边建立一个经济开发区。 题目描述 已知开发区的建筑地块是一个n×nn imes nn×n的矩形,而开发...

  •         Apache POI是一个开源的利用Java读写Excel,WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码:package com.xing.studyTest.poi;import java.io.FileInputSt...

  • 要取得[a,b)的随机整数,使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数,使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数,使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n;其中的a是起始值,n是整数的范围。 要取得a到b之间的...

  • 利用本征图像分解(Intrinsic Image Decomposition)算法,将图像分解为shading(illumination) image 和 reflectance(albedo) image,计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 题目:面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制: 1 <= 数组长度 <= 50000 解题: cl...

  • 题目:二叉搜索树的后序遍历序列 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树:      5     /    2   6   /  1   3示例 1: 输入: [1,6,3,2,5] 输出...