Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

Commit1a0a641

Browse files
committed
one more minimum path sum
1 parent2ccc7ee commit1a0a641

File tree

2 files changed

+32
-1
lines changed

2 files changed

+32
-1
lines changed

‎Medium/64-minimumPathSum.js‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/**
2+
* Dynamic programming: S[i][j] = min(S[i - 1][j], S[i][j - 1]) + grid[i][j]
3+
* Iniatially, S[i][j] is the sum of first row and first column elments.
4+
* Be careful, how JavaScript handles two demensional array, otherwise, you can get
5+
* 'undefined' error.
6+
*
7+
*@param {number[][]} grid
8+
*@return {number}
9+
*/
10+
varminPathSum=function(grid){
11+
varm=grid.length;
12+
varn=grid[0].length;
13+
varsum=[];
14+
sum[0]=[grid[0][0]];
15+
for(vari=1;i<m;i++){
16+
sum[i]=[sum[i-1][0]+grid[i][0]];
17+
}
18+
19+
for(varj=1;j<n;j++){
20+
sum[0][j]=sum[0][j-1]+grid[0][j];
21+
}
22+
23+
for(vari=1;i<m;i++){
24+
for(varj=1;j<n;j++){
25+
sum[i][j]=Math.min(sum[i-1][j],sum[i][j-1])+grid[i][j];
26+
}
27+
}
28+
29+
returnsum[m-1][n-1];
30+
};

‎README.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@
1515
*[28. Implement strStr()](https://leetcode.com/problems/implement-strstr/) -[Solution](./Easy/28-implementstrStr.js)
1616
*[38. Count and Say](https://leetcode.com/problems/count-and-say/) -[Solution](./Easy/38-countandSay.js)
1717
*[66. Plus One](https://leetcode.com/problems/plus-one/) -[Solution](./Easy/66-plusOne.js)
18-
*[66. Add Binary](https://leetcode.com/problems/add-binary/) -[Solution](./Easy/67-addBinary.js)
18+
*[67. Add Binary](https://leetcode.com/problems/add-binary/) -[Solution](./Easy/67-addBinary.js)
1919
*[70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/) -[Solution](./Easy/70-climbChairs.js)
2020
*[83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/) -[Solution](./Easy/83-removeDuplicatesFromSortedList.js)
2121
*[88. Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/) -[Solution](./Easy/88-mergeSortedArray.js)
@@ -69,6 +69,7 @@
6969
*[46. Permutations](https://leetcode.com/problems/permutations/) -[Solution](./Medium/46-permutations.js)
7070
*[53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/) -[Solution](./Medium/53-maximumSubarray.js)
7171
*[62.Unique Paths](https://leetcode.com/problems/unique-paths/) -[Solution](./Medium/62-uniquePaths.js)
72+
*[64.Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/) -[Solution](./Medium/64-minimumPathSum.js)
7273
*[77.Combinations](https://leetcode.com/problems/combinations/) -[Solution](./Medium/77-combinations.js)
7374
*[94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/) -[Solution](./Medium/94-binaryTreeInorder.js)
7475
*[96. Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/) -[Solution](./Medium/96-uniqueBinarySearchTrees.js)

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp