#
##
~
[triangle](https://leetcode-cn.com/problems/triangle/)
>
```text
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
```
112+3+5+1= 11
DFS
DFS
DFS
- DFS
- triangle ****
```go
func minimumTotal(triangle [][]int) int {
if len(triangle) == 0 || len(triangle[0]) == 0 {
return 0
}
// 1f[i][j] i,j
var l = len(triangle)
var f = make([][]int, l)
// 2
for i := 0; i < l; i++ {
for j := 0; j < len(triangle[i]); j++ {
if f[i] == nil {
f[i] = make([]int, len(triangle[i]))
}
f[i][j] = triangle[i][j]
}
}
// 3
for i := len(triangle) - 2; i >= 0; i-- {
for j := 0; j < len(triangle[i]); j++ {
f[i][j] = min(f[i+1][j], f[i+1][j+1]) + triangle[i][j]
}
}
// 4
return f[0][0]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
```
```go
//
// [
// [2],
// [3,4],
// [6,5,7],
// [4,1,8,3]
// ]
func minimumTotal(triangle [][]int) int {
if len(triangle) == 0 || len(triangle[0]) == 0 {
return 0
}
// 1f[i][j] 0,0i,j
var l = len(triangle)
var f = make([][]int, l)
// 2
for i := 0; i < l; i++ {
for j := 0; j < len(triangle[i]); j++ {
if f[i] == nil {
f[i] = make([]int, len(triangle[i]))
}
f[i][j] = triangle[i][j]
}
}
//
for i := 1; i < l; i++ {
for j := 0; j < len(triangle[i]); j++ {
//
// 1
// 2
if j-1 < 0 {
f[i][j] = f[i-1][j] + triangle[i][j]
} else if j >= len(f[i-1]) {
f[i][j] = f[i-1][j-1] + triangle[i][j]
} else {
f[i][j] = min(f[i-1][j], f[i-1][j-1]) + triangle[i][j]
}
}
}
result := f[l-1][0]
for i := 1; i < len(f[l-1]); i++ {
result = min(result, f[l-1][i])
}
return result
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
```
##
```go
Function(x) {
...
Funciton(x-1);
...
}
```
(Memorization Search)
##
-
- /Maximum/Minimum
- Yes/No
- Count(\*)
- Can not sort / swap
[longest-consecutive-sequence](https://leetcode-cn.com/problems/longest-consecutive-sequence/)
##
1. ** State**
-
2. Function
-
3. Intialization
- ,
4. Answer
-
##
1. Matrix DP (10%)
1. Sequence (40%)
1. Two Sequences DP (40%)
1. Backpack (10%)
>
>
> -
## 110%
### [minimum-path-sum](https://leetcode-cn.com/problems/minimum-path-sum/)
> *m*x*n*
1state: f[x][y] x,y
2function: f[x][y] = min(f[x-1][y], f[x][y-1]) + A[x][y]
3intialize: f[0][0] = A[0][0]f[i][0] = sum(0,0 -> i,0) f[0][i] = sum(0,0 -> 0,i)
4answer: f[n-1][m-1]
```go
func minPathSum(grid [][]int) int {
//
// f[i][j] i,j0,0
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
//
// f[i][0]f[0][j]
for i := 1; i < len(grid); i++ {
grid[i][0] = grid[i][0] + grid[i-1][0]
}
for j := 1; j < len(grid[0]); j++ {
grid[0][j] = grid[0][j] + grid[0][j-1]
}
for i := 1; i < len(grid); i++ {
for j := 1; j < len(grid[i]); j++ {
grid[i][j] = min(grid[i][j-1], grid[i-1][j]) + grid[i][j]
}
}
return grid[len(grid)-1][len(grid[0])-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
```
### [unique-paths](https://leetcode-cn.com/problems/unique-paths/)
> m x n Start
> Finish
>
```go
func uniquePaths(m int, n int) int {
// f[i][j] i,j0,0
f := make([][]int, m)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if f[i] == nil {
f[i] = make([]int, n)
}
f[i][j] = 1
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
f[i][j] = f[i-1][j] + f[i][j-1]
}
}
return f[m-1][n-1]
}
```
### [unique-paths-ii](https://leetcode-cn.com/problems/unique-paths-ii/)
> m x n Start
> Finish
>
>
```go
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
// f[i][j] = f[i-1][j] + f[i][j-1]
if obstacleGrid[0][0] == 1 {
return 0
}
m := len(obstacleGrid)
n := len(obstacleGrid[0])
f := make([][]int, m)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if f[i] == nil {
f[i] = make([]int, n)
}
f[i][j] = 1
}
}
for i := 1; i < m; i++ {
if obstacleGrid[i][0] == 1 || f[i-1][0] == 0 {
f[i][0] = 0
}
}
for j := 1; j < n; j++ {
if obstacleGrid[0][j] == 1 || f[0][j-1] == 0 {
f[0][j] = 0
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if obstacleGrid[i][j] == 1 {
f[i][j] = 0
} else {
f[i][j] = f[i-1][j] + f[i][j-1]
}
}
}
return f[m-1][n-1]
}
```
## 240%
### [climbing-stairs](https://leetcode-cn.com/problems/climbing-stairs/)
> *n*
```go
func climbStairs(n int) int {
// f[i] = f[i-1] + f[i-2]
if n == 1 || n == 0 {
return n
}
f := make([]int, n+1)
f[1] = 1
f[2] = 2
for i := 3; i
>
>
```go
func canJump(nums []int) bool {
//
// f[i] 0i
// f[i] = OR(f[j],j= i {
f[i] = true
}
}
}
return f[len(nums)-1]
}
```
### [jump-game-ii](https://leetcode-cn.com/problems/jump-game-ii/)
>
>
>
```go
// v1v2
func jump(nums []int) int {
// f[i]
// f[i] = f[j],a[j]+j >=i,min(f[j]+1)
// f[0] = 0
// f[n-1]
f := make([]int, len(nums))
f[0] = 0
for i := 1; i < len(nums); i++ {
// f[i] i
f[i] = i
// +1
for j := 0; j < i; j++ {
if nums[j]+j >= i {
f[i] = min(f[j]+1,f[i])
}
}
}
return f[len(nums)-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
```
```go
// v2 +
func jump(nums []int) int {
n:=len(nums)
f := make([]int, n)
f[0] = 0
for i := 1; i < n; i++ {
//
//
idx:=0
for idx
```go
func minCut(s string) int {
// state: f[i] "i"cut(-1)
// function: f[i] = MIN{f[j]+1}, j < i && [j+1 ~ i]
// intialize: f[i] = i - 1 (f[0] = -1)
// answer: f[s.length()]
if len(s) == 0 || len(s) == 1 {
return 0
}
f := make([]int, len(s)+1)
f[0] = -1
f[1] = 0
for i := 1; i b {
return b
}
return a
}
func isPalindrome(s string, i, j int) bool {
for i < j {
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}
```
-
### [longest-increasing-subsequence](https://leetcode-cn.com/problems/longest-increasing-subsequence/)
>
```go
func lengthOfLIS(nums []int) int {
// f[i] 0i
// f[i] = max(f[j])+1 ,a[j] b {
return a
}
return b
}
```
### [word-break](https://leetcode-cn.com/problems/word-break/)
> **** *s* **** *wordDict* *s*
```go
func wordBreak(s string, wordDict []string) bool {
// f[i] i
// f[i] = f[j] && s[j+1~i] in wordDict
// f[0] = true
// return f[len]
if len(s) == 0 {
return true
}
f := make([]bool, len(s)+1)
f[0] = true
max,dict := maxLen(wordDict)
for i := 1; i 0 {
l = i - max
}
for j := l; j < i; j++ {
if f[j] && inDict(s[j:i],dict) {
f[i] = true
break
}
}
}
return f[len(s)]
}
func maxLen(wordDict []string) (int,map[string]bool) {
dict := make(map[string]bool)
max := 0
for _, v := range wordDict {
dict[v] = true
if len(v) > max {
max = len(v)
}
}
return max,dict
}
func inDict(s string,dict map[string]bool) bool {
_, ok := dict[s]
return ok
}
```
0 length+1 f[n]
- i
- length+1
- index=i-1
- f[n] f[m][n]
## Two Sequences DP40%
### [longest-common-subsequence](https://leetcode-cn.com/problems/longest-common-subsequence/)
> text1 text2
>
> "ace" "abcde" "aec" "abcde"
```go
func longestCommonSubsequence(a string, b string) int {
// dp[i][j] aibj
// dp[m+1][n+1]
// ' a d c e
// ' 0 0 0 0 0
// a 0 1 1 1 1
// c 0 1 1 2 1
//
dp:=make([][]int,len(a)+1)
for i:=0;i
>
>
+1
```go
func minDistance(word1 string, word2 string) int {
// dp[i][j] aibj
// dp[i][j] = OR(dp[i-1][j-1]a[i]==b[j],min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1)
dp:=make([][]int,len(word1)+1)
for i:=0;iamount =>-1
dp:=make([]int,amount+1)
for i:=0;ib{
return b
}
return a
}
```
> dp[i-a[j]] a[j]
### [backpack](https://www.lintcode.com/problem/backpack/description)
> n m A[i]
```go
func backPack (m int, A []int) int {
// write your code here
// f[i][j] ij
// f[i][j] =f[i-1][j] f[i-1][j-a[i] j>a[i]
// f[0][0]=true f[...][0]=true
// f[n][X]
f:=make([][]bool,len(A)+1)
for i:=0;i `n` `m` . `A` `V` .
> ?
f[i][j] i j
```go
func backPackII (m int, A []int, V []int) int {
// write your code here
// f[i][j] ij
// f[i][j] =max(f[i-1][j] ,f[i-1][j-A[i]]+V[i]) A[i]
// f[0][0]=0 f[0][...]=0 f[...][0]=0
f:=make([][]int,len(A)+1)
for i:=0;i