# 2022-06-14

## [72. Edit Distance](https://leetcode.com/problems/edit-distance/)

### Description

Given two strings `word1` and `word2`, return *the minimum number of operations required to convert `word1` to `word2`*.

You have the following three operations permitted on a word:

* Insert a character
* Delete a character
* Replace a character

**Example 1:**

```
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
```

**Example 2:**

```
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
```

**Constraints:**

* `0 <= word1.length, word2.length <= 500`
* `word1` and `word2` consist of lowercase English letters.

### Solution

#### Approach #0

```go
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := 0; i < m+1; i++ {
        dp[i] = make([]int, n+1)
        dp[i][0] = i
    }
    for i := 0; i < n+1; i++ {
        dp[0][i] = i
    }

    for i := 1; i < m+1; i++ {
        for j := 1; j < n+1; j++ {
            a, b, c := dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]
            if word1[i-1] != word2[j-1] {
                c += 1
            }
            dp[i][j] = min(a, min(b, c))
        }
    }
    return dp[m][n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

#### Approach #1

```go
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([]int, n+1)
    for i := 0; i < n+1; i++ {
        dp[i] = i
    }

    var ld int
    for i := 1; i < m+1; i++ {
        ld = dp[0]
        dp[0] = i
        for j := 1; j < n+1; j++ {
            a, b, c := dp[j-1]+1, dp[j]+1, ld
            if word1[i-1] != word2[j-1] {
                c += 1
            }
            ld = dp[j]
            dp[j] = min(a, min(b, c))
        }
    }
    return dp[n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

## [322. Coin Change](https://leetcode.com/problems/coin-change/)

### Description

You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money.

Return *the fewest number of coins that you need to make up that amount*. If that amount of money cannot be made up by any combination of the coins, return `-1`.

You may assume that you have an infinite number of each kind of coin.

**Example 1:**

```
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
```

**Example 2:**

```
Input: coins = [2], amount = 3
Output: -1
```

**Example 3:**

```
Input: coins = [1], amount = 0
Output: 0
```

**Constraints:**

* `1 <= coins.length <= 12`
* `1 <= coins[i] <= 2^31 - 1`
* `0 <= amount <= 10^4`

### Solution

#### Approach #0

```go
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := 1; i < amount+1; i++ {
        dp[i] = amount + 1
    }
    for i := 1; i <= amount; i++ {
        for _, v := range coins {
            if v <= i {
                dp[i] = min(dp[i], dp[i-v]+1)
            }
        }
    }
    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

## [343. Integer Break](https://leetcode.com/problems/integer-break/)

### Description

Given an integer `n`, break it into the sum of `k` **positive integers**, where `k >= 2`, and maximize the product of those integers.

Return *the maximum product you can get*.

**Example 1:**

```
Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
```

**Example 2:**

```
Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
```

**Constraints:**

* `2 <= n <= 58`

### Solution

#### Approach #0

```go
func integerBreak(n int) int {
    dp := make([]int, n+1)
    for i := 2; i <= n; i++ {
        var cur int
        for j := 1; j < i; j++ {
            cur = max(cur, max(j*(i-j), j*dp[i-j]))
        }
        dp[i] = cur
    }
    return dp[n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

## [498. Diagonal Traverse](https://leetcode.com/problems/diagonal-traverse/)

### Description

Given an `m x n` matrix `mat`, return *an array of all the elements of the array in a diagonal order*.

**Example 1:**

![](https://img.content.cc/a/2022/06/14/14-21-57-121-9fb789fa7f0058abb43d383316bbf442-c2a0bc.png)

```
Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]
```

**Example 2:**

```
Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]
```

**Constraints:**

* `m == mat.length`
* `n == mat[i].length`
* `1 <= m, n <= 10^4`
* `1 <= m * n <= 10^4`
* `-10^5 <= mat[i][j] <= 10^5`

### Solution

#### Approach #0

```go
func findDiagonalOrder(mat [][]int) []int {
    m, n := len(mat), len(mat[0])
    ans := make([]int, 0, m*n)
    for i := 0; i < m+n-1; i++ {
        if i%2 == 1 {
            x := max(i-n+1, 0)
            y := min(i, n-1)
            for x < m && y >= 0 {
                ans = append(ans, mat[x][y])
                x++
                y--
            }
        } else {
            x := min(i, m-1)
            y := max(i-m+1, 0)
            for x >= 0 && y < n {
                ans = append(ans, mat[x][y])
                x--
                y++
            }
        }
    }
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```