今日任务：

1. LeetCode343 整数拆分
2. LeetCode96 不同的二叉搜索树



资料来源：

1. [代码随想录 | LeetCode343 整数拆分](https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.htmlhttps://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html)
2. [代码随想录 | LeetCode96 不同的二叉搜索树](https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html)

### 1 LeetCode343 整数拆分

:::info{title="题目"}
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

 

示例 1:
```
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
```
示例 2:
```
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
```

提示:

- 2 <= n <= 58
:::

先明确dp数组的含义：**对于下标i，dp[i]所储存的就是数字i的拆分数字的乘积最大值**。它的递推思路就是，对于每个数字i来说，它都需要进行下一层从1到i- 1的循环j，每次循环都要比较当前已经存储的最大乘积，j * (i - j)（仅分拆一次）和j * (i - j)位置的最大乘积。

举例来说，对于数字4，它所需要在循环中查找的就是：

```
1 * 3 -> 这个代表分拆成两个数字
1 * dp[3] -> 注意dp[3]的含义：数字3的拆分数字的成绩最大值 这个代表分拆成多个数字
2 * 2
2 * dp[2] 注意 从中间数字开始之后的循环时可以优化的
3 * 1
3 * dp[1]
```

:::tip{title="提示"}
这题也有一个数论解法，即每次都分拆3，如果剩下的是4就停止分拆，否则继续分拆3，直到产生余数。这个解法有个印象就行。
:::

``` go
func integerBreak(n int) int {
    dp_array := make([]int, n+1)
    dp_array[2] = 1
    for i := 3; i <= n; i++ {
        for j := 1; j < i; j++ { // 第二层循环 这个循环从1还是从2开始都可以 因为分拆1必然不可能是最大值
            dp_array[i] = max(dp_array[i], j*(i-j), j*dp_array[i-j])
        }
    }

    return dp_array[n]
}
```

``` java
class Solution {
    public int integerBreak(int n) {
        int[] dp_array = new int[n + 1];
        dp_array[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp_array[i] = Integer.max(dp_array[i], Integer.max(j * (i - j), j * dp_array[i - j]));
            }
        }
        return dp_array[n];
    }
}
```

``` python
class Solution:
    def integerBreak(self, n: int) -> int:
        dp_array = [0] * (n + 1)
        dp_array[2] = 1
        for i in range(3, n + 1):
            for j in range(2, i):
                dp_array[i] = max(dp_array[i], j * (i - j), j * dp_array[i - j])
        return dp_array[n]
```        

### 2 LeetCode96 不同的二叉搜索树

:::info{title="题目"}
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

 

示例 1：
```
输入：n = 3
输出：5
```
示例 2：
```
输入：n = 1
输出：1
```

提示：

- 1 <= n <= 19
:::

这个题可以被转化为：n个节点组成二叉树的可能的树的形状有多少。还是先明确dp数组的含义：**对于下标i，dp[i]表示i个节点组成的互不相同的树的种类**。再说递推关系：如果按照题意理解，那么对于任意的节点数量n，它有可能组成的搜索二叉树的种类数量包括从数字1开始到数字n作为根节点的所有搜索二叉树，每个根节点对应的左子树和右子树的数量分别为j和i - 1 - j（j >= 0）。

举例来说，如果要求的n为4时，它所能组成的搜索二叉树如下：

![9baf1caf00134be9b55ceada1f19f5a.jpg](https://www.misaka19327.cc/static/img/1c49e96f4018122fe0d296750fd64066.9baf1caf00134be9b55ceada1f19f5a.jpg)

可知dp数组元素之间的递推关系。


``` go
func numTrees(n int) int {
    dp_array := make([]int, n+1)
    dp_array[0] = 1
    for i := 1; i <= n; i++ { // 针对每个节点数
        for j := 1; j <= i; j++ { // 对于每个节点数i来说 要算的是0 * (i - 1)循环到(i - 1) * 0
            dp_array[i] += dp_array[j-1] * dp_array[i-j]
        }
    }

    return dp_array[n]
}
```

``` java
class Solution {
    public int numTrees(int n) {
        int[] dp_array = new int[n + 1];
        dp_array[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) { // 0 * i - 1 到i - 1 * 0
                dp_array[i] += dp_array[j] * dp_array[i - 1 - j];
            }
        }

        return dp_array[n];
    }
}
``` 

``` python
class Solution:
    def numTrees(self, n: int) -> int:
        dp_array = [0] * (n + 1)
        dp_array[0] = 1
        for i in range(1, n + 1):
            for j in range(0, i):
                dp_array[i] += dp_array[j] * dp_array[i - 1 - j]
        return dp_array[n]
```

代码随想录算法训练营第四十一天 | LeetCode343 整数拆分、LeetCode96 不同的二叉搜索树

记录Go语言的基础语法和基本知识。



> Go语言是Google开发的一种**静态强类型、编译型**、并发型，并**具有垃圾回收功能**的编程语言。

### 1 HelloWorld

``` go
// helloWorld.go
package main

import {
    "fmt"
}

func main() {
    fmt.Println("Hello World!\n")
}
```

注意，Go语言使用包来组织代码，一个包可以提供一些类型和方法来给其他包使用。

**Go语言的唯一程序执行入口，只在main包里的main函数。**

### 2 变量与内置数据类型

**声明变量语法**：

``` go
var i int // 仅声明
var j int = 1 // 声明并且赋值
var k = 1 // 声明并且赋值 类型支持自动推导
l := 1 // 声明并且赋值
```

注意Go语言的类型声明在变量名后面。

****

**简单类型**：

- 空值：nil
- 整型：int，uint8，uint16，uint32，int8，int16，int32...
- 浮点型：float32，float64
- 字节型：byte（等效uint8）
- 字符串类型：string
- 布尔型：boolean

****

**字符串**：

在Go中，字符串类型变量一般使用UTF-8编码，并且使用uint8数组来保存字符，英文一个字符占8个字节，中文一般情况下占3个字节。所以在中英文混合的字符串中，如果打印字符串中中文的任意一个位置，大概率打出来也是乱码。这种情况下，如果需要打印其中的中文字符，需要将其转换为rune数组：

``` go
str2 := "Go语言"
runeArr := []rune(str2)
fmt.Println(reflect.TypeOf(runeArr[2]).Kind()) // 查看类型 int32
fmt.Println(runeArr[2], string(runeArr[2]))    // 35821 语
fmt.Println("len(runeArr)：", len(runeArr))    // len(runeArr)： 4
```

转换为rune数组后，字符串中的每个字符都会被以int32来存储，因此可以正确处理中文。

****

**数组、切片：**

声明数组：

``` go
package main

import "fmt"

func main() {
	var array = [5]int{} // 声明一维int数组
	var array2 = [5][2]int{} // 声明二维int数组
	fmt.Println(array) // [0 0 0 0 0]
	fmt.Println(array2) // [[0 0] [0 0] [0 0] [0 0] [0 0]]
	var array3 = [5]int{1, 2, 3, 4, 5} // 声明并且赋值
	fmt.Println(array3) // [1 2 3 4 5]
	array3[1] = 10 // 根据下标修改值
	fmt.Println(array3) // [1 10 3 4 5]
}
```

数组是定长的，如果想要像python的list一样灵活的数组，可以使用切片：

``` go
package main

import "fmt"

func main() {
	slice := make([]int, 5) // 声明一个长度为5的切片
	slice2 := make([]int, 5, 10) // 声明一个长度为5 容量为10的切片
	fmt.Println(slice) // [0 0 0 0 0]
	fmt.Println(slice2) // [0 0 0 0 0]
        // len函数访问长度 cap函数访问容量
	fmt.Println(len(slice), cap(slice)) // 5 5
	fmt.Println(len(slice2), cap(slice2)) // 5 5
}
```

一个切片有3个重要的部分：长度、容量、指向这个切片的指针。对于切片来说，无论是长度还是容量都可以随时扩展。

``` go
package main

import "fmt"

func main() {
	slice2 := make([]int, 5, 10) // 声明切片
	slice2 = append(slice2, 1, 2, 3, 4, 5, 6, 7) // 为切片添加元素
	fmt.Println(slice2) // [0 0 0 0 0 1 2 3 4 5 6 7]
	fmt.Println(len(slice2), cap(slice2)) // 12 20
	sub1 := slice2[3:] // 为切片进行切片
	sub2 := slice2[4:6] // 同上
	combined := append(sub1, sub2...) // 合并切片 切片后面加... 是解包的写法
	fmt.Println(combined) // [0 0 1 2 3 4 5 6 7 0 1]
}
```

****

**字典：**

各方面同python的dict。

``` go
package main

import "fmt"

func main() {
	map1 := map[string]string{} // 声明 []里面是键类型 外面是值类型
	fmt.Println(map1) // map[]
	map2 := map[string]int{ // 声明并且赋值
		"test": 1,
		"test2": 2,
	}
	fmt.Println(map2) // map[test:1 test2:2]
	map2["test2"] = 3 // 赋值/修改值
	fmt.Println(map2) // map[test:1 test2:3]
}
```

****

**指针：**

对，就是那个指针。

``` go
package main

import "fmt"

func main() {
	str := "golang"
	var pointer *string = &str // 获取指针 指针类型就是原类型前面加星号 获取一个变量的指针使用&
	*pointer = "hello" // 在指针前加星号 等效这个指针指向的变量
	fmt.Println(pointer) // 0xc000026070
	fmt.Println(str) // hello
}
```

函数参数会用指针。如果参数类型不是指针类型，那么实际传进去的是参数的副本，不影响参数本身；反之传入了指针的话，就能对这个变量直接进行修改。

### 3 流程控制

**if-else：**

``` go
age := 18
if age < 18 {
    fmt.Printf("Kid")
} else {
    fmt.Printf("Adult")
}

// 可以简写为：
if age := 18; age < 18 { // 赋值语句和判断语句在一起也没问题
    fmt.Printf("Kid")
} else {
    fmt.Printf("Adult")
}
```

****

**switch：**

不需要break。如果需要向下执行下面的分支的话，可以加fallthrough关键字

``` go
package main

import "fmt"

func main() {
	a := 1
	switch a {
	case 1: { // 这个冒号后面的大括号可以省略
		fmt.Println("1") // 1
                // 如果在这里加fallthrough关键字 那么下面分支都会被执行
	}
	case 2: {
		fmt.Println("2")
	}
	default: {
		fmt.Println("default")
	}
	}
}
```

****

**for：**

``` go
sum := 0
for i := 0; i < 10; i++ {
    if sum > 50 {
        break
    }
    sum += i
}
```

Go还支持直接对数组，切片和字典进行遍历：

``` go
nums := []int{10, 20, 30, 40}
for i, num := range nums { // 这个遍历方式好评
	fmt.Println(i, num)
}
// 0 10
// 1 20
// 2 30
// 3 40
m2 := map[string]string{
	"Sam":   "Male",
	"Alice": "Female",
}

for key, value := range m2 {
	fmt.Println(key, value)
}
// Sam Male
// Alice Female
```

### 4 函数

Go里面的函数支持多个返回值。一个简单的函数定义如下：

``` go
func test(i int, j int) (int, int) { // 先是参数 后是返回值 返回值只有一个的时候可以不要括号 也可以没有返回值
	return i + j, i - j
}
```

return也可以配合返回值这么写：

``` go
func test2 (i int) (a int){ // 直接在返回处定义一个变量 在函数内对这个变量进行操作 直接返回
	a = i
	return 
}
```

****

**异常处理：**

Go的异常处理和其他语言有比较大的差异，反而和c语言可能有点像。

``` go
package main

import (
    "errors"
    "fmt"
)

func main() {
    if j, e := test("1"); e != nil { // 如果函数运行正常 那么e就是nil 如果被赋值了 那就表示有异常
        fmt.Println(e)
    } else {
        fmt.Println(j)
    }
}

func test(i string) (j string, e error) { // 返回值里除了正常返回的值 还有返回的异常
    if len(i) < 2 {
        e = errors.New("string is too short") // 返回异常
        return
    }
    j = i + "test"
    return // 正常返回
}
```

这种错误属于那种“可以被预估的”异常，还有一种不可预估的异常，会直接中断Go程序的运行，这被称为Panic。

``` go
package main

import "fmt"

func main() {
	fmt.Println(get(5)) // 数组越界
}

func get(i int) int {
	array := [3]int{1, 2, 3}
	return array[i]
}

// 报错：
// panic: runtime error: index out of range [5] with length 3

// goroutine 1 [running]:
// main.get(...)
// 	C:/Users/Misaka19327/OneDrive/Projects/GoLandProjects/Test/src/test2.go:11
// main.main()
// 	C:/Users/Misaka19327/OneDrive/Projects/GoLandProjects/Test/src/test2.go:6 +0x18
```

与try-catch类似的，Go有defer和recover两个关键字用来处理Panic。

``` go
package main

import "fmt"

func main() {
    fmt.Println(get(5))
    fmt.Println("Finished!")
}

func get(i int) (result int) {
    defer func() { // 异常处理函数
        if r := recover(); r != nil { // r即为报错信息
            fmt.Println(r)
            result = -1 // 直接返回-1 不继续执行
        }
    }() // 这个函数声明之后必须马上调用
    array := [3]int{1, 2, 3}
    return array[i]
}

// 运行结果：
// runtime error: index out of range [5] with length 3
// -1
// Finished!
```

在程序运行中，如果触发了Panic，程序控制权会直接移交给defer函数，defer函数中可以使用recover函数来使程序恢复运行。

### 5 结构体、方法、接口

Go语言中没有特别明确的类的概念，可以通过结构体的方式来近似的实现类的功能。

``` go
package main

import "fmt"

type ClassTest struct { // 结构体当类用
    property1 string
    property2 string
}

func (classTest *ClassTest) classMethodTest(param1 string) (result string) { // 类方法 其实它就是传入了一个结构体的指针来近似的实现类方法的效果
    result = param1 + classTest.property1
    return
}

func main() {
    classTest := &ClassTest{ // 实例化一个类（结构体）
        property1: "111",
        property2: "222",
    }
    classTest.property2 = "333" // 修改类（结构体）的成员变量
    fmt.Println(classTest.property2)
    result := classTest.classMethodTest("1") // 调用方法
    fmt.Println(result)
}

// 结果：
// 333
// 1111
```

:::tip{title="提示"}
注意，`func (class *Class) classMethod`和`func (class Class) classMethod`两者并不等效。除了之前函数里说过的，传入的是指针和传入的是值本身的区别以外，前者只会被实例化的类的指针变量调用，后者只会被实例化的类的变量调用。只是Go语言做了优化，对于可寻址的被实例化的类的变量，依然可以调用前者，只是传入的仍然是指针。

对于上例来说，`classTest.classMethodTest("1")`实际执行的是`*(classTest).classMethodTest("1")`。

这两种写法的函数（暂且叫作指针方法和值方法），大部分情况下都是指针方法更加常用，只有在类不算大且不对类的成员进行修改的情况下，可以创建值方法。
:::

类还可以通过new函数来实例化：`classTest2 = new(ClassTest)`，只是此时的实例内部的成员变量全部都是默认值。

****

**接口：**

定义了一组方法的集合，就能叫接口。这个接口不需要继承，直接实现就行。

``` go
package main

import "fmt"

type interfaceTest interface { // 定义接口 下面是两个方法和返回值
    getAttr1() string
    getAttr2() string
}

type classFromInterface struct { // 定义类 实现接口
    attr1 string
    attr2 string
}

func (c *classFromInterface) getAttr1() string { // 实现方法1
    return c.attr1
}

func (c *classFromInterface) getAttr2() string { // 实现方法2
    return c.attr2
}

func getClassFromInterface(attr1 string, attr2 string) (result *classFromInterface) { // 类的构造方法 返回一个指针
    result = &classFromInterface{
        attr2: attr2,
        attr1: attr1,
    }
    return
}

func main() {
    var class interfaceTest = getClassFromInterface("111", "222") // 获取类指针
    fmt.Println(class.getAttr2()) // 调用接口方法
    fmt.Println(class.getAttr1()) // 调用接口方法
}
```

:::tip{title="提示"}
注意，如果不创建并且使用一个类，Go语言并不会检查这个类是否全部实现了一个接口。就上例来说，想检查这一点可以通过类似`var _ interfaceTest = (*classFromInterface)(nil)`来让Go在编译期就检查是否全部实现了接口。

这条语句的意思是，将空值转换为*classFromInterface类型，再转换为interfaceTest接口，如果转换失败，说明classFromInterface类并没有实现interfaceTest接口的所有方法。

接口和实例可以互相强制转换。
:::

****

**空接口：**

如果一个接口里没有任何的方法，那么这个接口可以代表任意类型。

``` go
func main() {
	m := make(map[string]interface{})
	m["name"] = "Tom"
	m["age"] = 18
	m["scores"] = [3]int{98, 99, 85}
	fmt.Println(m) // map[age:18 name:Tom scores:[98 99 85]]
}
```

### 6 包，模块

一般来说，一个文件夹即可作为一个包，包内的方法，变量，类，方法互相可见。如果想让一个方法/类对包外也可见，需要将其首字母大写。如果首字母小写，它就是一个类似private的状态。包之间互相调用也需要import。

Go语法入门

今日任务：

1. LeetCode62 不同路径
2. LeetCode63 不同路径 Ⅱ



资料来源：

1. [代码随想录 | LeetCode62 不同路径](https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html)
2. [代码随想录 | LeetCode63 不同路径 Ⅱ](https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html)

### 1 LeetCode62 不同路径

:::info{title="题目"}
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

 

示例 1：

![image.png](https://www.misaka19327.cc/static/img/e4564ba9068dbdc6ae566243f89e7fc6.image.png)
```
输入：m = 3, n = 7
输出：28
```
示例 2：
```
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
```
示例 3：
```
输入：m = 7, n = 3
输出：28
```
示例 4：
```
输入：m = 3, n = 3
输出：6
```

提示：

- 1 <= m, n <= 100
- 题目数据保证答案小于等于 $$2 * 10 ^ 9$$
:::

很经典的两层数组的动态规划，还是按照动态规划五部曲走：

1. dp数组的含义和下标含义：从起点到达当前位置的可能的路径数量
2. 确定递推公式：`dp_array[i][j] = dp_array[i - 1][j] + dp_array[i][j - 1]`
3. dp数组初始化：第一横行和第一竖行全部初始化为1，意味着从起点到达这些点的可能路径只有1条。由于n，m可能为1，所以`dp_array[0][0]`也得初始化为1
4. 确定遍历顺序：先行后列还是先列后行没有影响
5. 举例推导：以用例1为例，它的dp数组应该是：
    
    | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
    | --- | --- | --- | --- | --- | --- | --- |
    | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
    | 1 | 3 | 6 | 10 | 15 | 21 | 28 |
    
    可见没有问题
    
:::tip{title="提示"}
另外，这题还有一个数论的解法。首先，对于给定的m，n，从起点走到终点一定会走$$m + n - 2$$步，而且其中一定有$$m - 1$$步是向下走的，别管什么时候向下走。那也就是说，这题可以转化为一个数学问题：在$$m + n - 2$$个数中，挑出$$m - 1$$个数，可以有多少种挑法？结果就是$$C^{m - 1}_{m + n - 2}$$。
:::


``` python
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 初始化
        dp_array = [[0] * n] * m
        for i in range(n):
            dp_array[0][i] = 1
        for i in range(m):
            dp_array[i][0] = 1

        # 开始dp
        for i in range(1, m):
            for j in range(1, n):
                dp_array[i][j] = dp_array[i - 1][j] + dp_array[i][j - 1]

        return dp_array[-1][-1]
```

``` java
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp_array = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp_array[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp_array[0][i] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp_array[i][j] = dp_array[i - 1][j] + dp_array[i][j - 1];
            }
        }
        return dp_array[m - 1][n - 1];
    }
}
```

``` go
func uniquePaths(m int, n int) int {
    dpArray := make([][]int, m)
    for i := range dpArray {
        dpArray[i] = make([]int, n)
        dpArray[i][0] = 1
    }
    for i := range dpArray[0] {
        dpArray[0][i] = 1
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dpArray[i][j] = dpArray[i - 1][j] + dpArray[i][j - 1]
        }
    }
    return dpArray[m - 1][n - 1]
}
```

### 2 LeetCode63 不同路径 Ⅱ

:::info{title="题目"}
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

![image.png](https://www.misaka19327.cc/static/img/92f6af59950f735b340f54e9b4052c82.image.png)
```
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
```
示例 2：
```
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
```

提示：

- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] 为 0 或 1
:::

~~不是，这题给的用例也太坑，完全看不出来这二维数组是按行存的还是按列存的气死个人。~~

这题的思路和上面的62是完全一致的，但是有的地方不一样。一方面是遍历dp数组的过程中，如果遇到障碍，说明这块是永远不可抵达的，所以要将其置为0；另一方面是初始化dp数组的过程中，如果遇到障碍，那么从这个障碍之后的所有位置都要置0，因为初始化的那一行/列本来就只有一条路，有个障碍在那里直接就把这一条路堵死了。

``` python
from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if obstacleGrid[0][0] == 1:
            return 0
        # 这题的obstacleGrid是按列存的 obstacleGrid[i]代表的是一列的数据 注意
        # 初始化
        for i in range(1, len(obstacleGrid)):  # 因为是一旦遇到障碍 后面赋值为0 所以不能从头开始循环 否则下一个初始化会有问题
            if obstacleGrid[i][0] == 0:
                obstacleGrid[i][0] = 1
            else:
                # 一旦遇到障碍 后面全部赋值为0
                obstacleGrid[i][0] = 0
                if i < len(obstacleGrid) - 1:
                    obstacleGrid[i + 1][0] = 1
        for i in range(len(obstacleGrid[0])):
            if obstacleGrid[0][i] == 0:
                obstacleGrid[0][i] = 1
            else:
                obstacleGrid[0][i] = 0
                if i < len(obstacleGrid[0]) - 1:
                    obstacleGrid[0][i + 1] = 1

        for i in range(1, len(obstacleGrid)):
            for j in range(1, len(obstacleGrid[0])):
                if obstacleGrid[i][j] == 1:
                    obstacleGrid[i][j] = 0
                else:
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]

        return obstacleGrid[-1][-1]
```

``` java
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) return 0;
        for (int i = 1; i < obstacleGrid.length; i++) {
            if (obstacleGrid[i][0] == 0) {
                obstacleGrid[i][0] = 1;
            } else {
                obstacleGrid[i][0] = 0;
                if (i < obstacleGrid.length - 1) {
                    obstacleGrid[i + 1][0] = 1;
                }
            }
        }
        for (int i = 0; i < obstacleGrid[0].length; i++) {
            if (obstacleGrid[0][i] == 0) {
                obstacleGrid[0][i] = 1;
            } else {
                obstacleGrid[0][i] = 0;
                if (i < obstacleGrid[0].length - 1) {
                    obstacleGrid[0][i + 1] = 1;
                }
            }
        }

        for (int i = 1; i < obstacleGrid.length; i++) {
            for (int j = 1; j < obstacleGrid[0].length; j++) {
                if (obstacleGrid[i][j] == 0) {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                } else {
                    obstacleGrid[i][j] = 0;
                }
            }
        }
        return obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    }
}
```

``` go
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	for i := 1; i < len(obstacleGrid); i++ {
		if obstacleGrid[i][0] == 1 {
			obstacleGrid[i][0] = 0
			if i < len(obstacleGrid) - 1 {
				obstacleGrid[i+1][0] = 1
			}
		} else {
			obstacleGrid[i][0] = 1
		}
	}
	for i := 0; i < len(obstacleGrid[0]); i++ {
		if obstacleGrid[0][i] == 1 {
			obstacleGrid[0][i] = 0
			if i < len(obstacleGrid[0]) - 1 {
				obstacleGrid[0][i + 1] = 1
			}
		} else {
			obstacleGrid[0][i] = 1
		}
	}
	for i := 1; i < len(obstacleGrid); i++ {
		for j := 1; j < len(obstacleGrid[0]); j++ {
			if obstacleGrid[i][j] == 1 {
				obstacleGrid[i][j] = 0
			} else {
				obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
			}
		}
	}
	return obstacleGrid[len(obstacleGrid) - 1][len(obstacleGrid[0]) - 1]
}
```

代码随想录算法训练营第三十九天 | LeetCode62 不同路径、LeetCode63 不同路径 Ⅱ

今日任务：

1. 动态规划理论基础
2. LeetCode509 斐波那契数
3. LeetCode70 爬楼梯
4. LeetCode746 使用最少花费爬楼梯



资料来源：

1. [代码随想录 | 动态规划理论基础](https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html)
2. [代码随想录 | LeetCode509 斐波那契数](https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html)
3. [代码随想录 | LeetCode70 爬楼梯](https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html)
4. [代码随想录 | LeetCode746 使用最少花费爬楼梯](https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html)

### 1 动态规划理论基础

先贴个图在这：

![image.png](https://www.misaka19327.cc/static/img/cf61ebaae6d72145d1f32ed06835df6a.image.png)

动态规划算法，是用于解决由许多重叠子问题组成的问题的算法。动态规划中，每个状态都是由上一个状态推导而来，这一点区别于贪心算法。比如说背包问题，动态规划每次都需要根据上一个状态来确定下一次拿什么物品，而贪心算法就不用，贪心直接可着最有价值的拿就是了。

动态规划五部曲：

1. 确定dp数组和下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

### 2 LeetCode509 斐波那契数

:::info{title="题目"}
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

 

示例 1：
```
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
```
示例 2：
```
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
```
示例 3：
```
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
```

提示：

- 0 <= n <= 30
:::

一道简单的动态规划。按照五部曲走就是：

1. 确定dp数组及下标含义：存储斐波那契数，每个下标对应该下标的斐波那契数
2. 确定递推公式：`array[i] = array[i - 1] + array[i - 2]`
3. dp数组如何初始化：第1个和第2个元素初始化为0和1
4. 确定遍历顺序：从前向后
5. 举例推导dp数组：0，1，2，3，5，8，13，21，34，55，没有问题。

``` python
class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        dp_array = [0] * (n + 1)
        dp_array[1] = 1
        for i in range(2, n + 1):
            dp_array[i] = dp_array[i - 1] + dp_array[i - 2]
        return dp_array[-1]
```        

### 2 LeetCode70 爬楼梯

:::info{title="题目"}
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

 

示例 1：
```
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
```
示例 2：
```
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
```

提示：

- 1 <= n <= 45
:::

同斐波那契数。另外这道题还有个plus版本，就是如果一次能爬的台阶有1或2或3或4或...或m个，那么有多少种爬楼的方法。这个只需要在递推那块反向遍历一下，取前m个台阶位置的走法的和即可。

``` python
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        dp_array = [0] * n
        dp_array[0] = 1
        dp_array[1] = 2
        for i in range(2, n):
            dp_array[i] = dp_array[i - 1] + dp_array[i - 2]
        return dp_array[-1]
```        

### 3 LeetCode746 使用最少花费爬楼梯

:::info{title="题目"}
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

 

示例 1：
```
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
```
示例 2：
```
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
```

提示：

- 2 <= cost.length <= 1000
- 0 <= cost[i] <= 999
:::

爬楼梯的plus版本。还是按五部曲走：

1. dp数组和下标的含义：到达第i个台阶时所花费的最少费用
2. 确定递推公式：`array[i] = min(cost[i - 1] + array[i - 1], cost[i - 2] + array[i - 2])`
3. dp数组初始化：题目给定的是从下标为0的台阶和下标为1的台阶出发都可以，那么array[0]和array[1]花费都为0，初始化为0
4. 遍历顺序：从前往后
5. 举例推导dp数组：示例1，0，0，15，没有问题

``` python
from typing import List

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp_array = [0] * (len(cost) + 1)
        for i in range(2, len(dp_array)):
            dp_array[i] = min(dp_array[i - 1] + cost[i - 1], dp_array[i - 2] + cost[i - 2])
        return dp_array[-1]
```

代码随想录算法训练营第三十八天 | LeetCode509 斐波那契数、LeetCode70 爬楼梯、LeetCode746 使用最少花费爬楼梯

今日任务：

1. LeetCode738 单调递增的数字
2. LeetCode968 监控二叉树
3. 贪心算法总结



资料来源：

1. [代码随想录 | LeetCode738 单调递增的数字](https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html)
2. [代码随想录 | LeetCode968 监控二叉树](https://programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html)
3. [代码随想录 | 贪心算法总结](https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E7%AF%87.html)

### 1 LeetCode738 单调递增的数字

:::info{title="题目"}
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

 

示例 1:
```
输入: n = 10
输出: 9
```
示例 2:
```
输入: n = 1234
输出: 1234
```
示例 3:
```
输入: n = 332
输出: 299
```

提示:

- 0 <= n <= $$10 ^ 9$$
:::

这题一开始看的时候的想法就是，这跟贪心有关系吗，不知道怎么贪。在看示例3的时候有了感觉，从后往前检查，如果有遇到**不是单调的两个数字，比它小的最大的数字一定是较大的数位-1，较小的数位为9的**。比如说332，从后往前检查的第一个就是2和3，如果要找比它小的而且是单调的，那么一定是2变成9，3变成2，这样整体就变成了329，再继续检查这个新的2和3，2 -> 9，3 -> 2，就得到了299。

另外，一旦有一个数位被置为9，那么比它小的所有数位都需要再置为9，以保证之前检查过的数位的单调性。比如说100，第一次检查0和0，是单调的；第二次检查1和0的时候就不是单调的了，这时需要将1 -> 0，0 -> 9，那么此时这个数字整体就是90，但是它不是单调数字，之前检查过的0失去了单调性，需要重新置为9。

``` python
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        n = str(n)
        n = list(n)
        n.reverse()
        n = list(map(int, n))
        
        pointer_9 = 0  # 列表已经反转 终点即是起点
        for i in range(len(n) - 1):
            if n[i] < n[i + 1]:
                pointer_9 = i
                n[i] = 9
                n[i + 1] -= 1

        for i in range(pointer_9):  # 按反转顺序来 置9
            n[i] = 9
            
        n.reverse()
        n = list(map(str, n))
        return int("".join(n))
```

### 2 LeetCode968 监控二叉树

:::info{title="题目"}
给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

 

示例 1：
```
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
```
示例 2：
```
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
```
提示：

- 给定树的节点数的范围是 [1, 1000]。
- 每个节点的值都是 0。
:::

这题的贪心很容易想到，那就是所有的叶子节点不能有摄像头，从叶子节点的父节点一级开始，竖方向上每隔两个节点设置一个摄像头，直到根节点。

首先，从上往下肯定是后序遍历没跑了；其次，因为给定的二叉树并没有限制对二叉树的读写，所以可以在遍历中使用。一个节点，它的状态可以是未覆盖、已被覆盖或者已设置摄像头三种情况。如果要实现思路，首先遍历中遇见叶子节点肯定是直接跳了；其次，如果左节点和右节点都是已覆盖区域，也可以直接跳过，由该节点的父节点来设置摄像头，这样就达成了“**竖方向上每隔两个节点设置一个摄像头**”；之后，如果左节点/右节点有未覆盖区域，那么为了保证所有区域都被覆盖，该节点必须设置一个摄像头；最后，如果左节点/右节点有摄像头，则设置该节点为已覆盖。注意后两个判断顺序不能变，防的就是一个节点的子节点一个有摄像头，一个是未覆盖，这时候必须给该节点上一个摄像头。

最后，因为检查都是对该节点的子节点进行检查，所以根节点并没有被检查过，所以最后必须给根节点单独检查是否是未覆盖，如果是就给根节点多加一个摄像头。（也可以给根节点多加一个虚拟的父节点，从虚拟父节点开始后序遍历来解决）

``` python
from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        if root.left is None and root.right is None:
            return 1
        monitor_number = 0
        stack = deque()
        stack.append(root)
        while len(stack) > 0:
            node = stack.pop()
            if node is None:
                node = stack.pop()
                # 规定0是未覆盖 1是有覆盖 2是有摄像头
                if node.left is None and node.right is None:
                    continue  # 叶子节点 不作处理
                if (node.left is not None and node.left.val == 1) and (node.right is not None and node.right.val == 1):
                    continue  # 左节点和右节点都是覆盖区域 不作处理
                if (node.left is not None and node.left.val == 0) or (node.right is not None and node.right.val == 0):
                    monitor_number += 1
                    node.val = 2
                    continue  # 左节点/右节点有未覆盖区域
                # 先检查子节点是否有未覆盖区域 再检查子节点有无摄像头 保证优先对未覆盖区域进行覆盖
                if (node.left is not None and node.left.val == 2) or (node.right is not None and node.right.val == 2):
                    node.val = 1
                    continue  # 左节点/右节点有摄像头 修改状态为有覆盖
            else:
                stack.append(node)
                stack.append(None)
                if node.right is not None:
                    stack.append(node.right)
                if node.left is not None:
                    stack.append(node.left)
        if root.val == 0:  # 因为遍历时都是对遍历节点的子节点进行检查 所以根节点并没有检查过是否被覆盖 在这里进行检查
            monitor_number += 1
        return monitor_number
```

### 3 贪心算法总结

贪心没有框架，没有显著的题目特征，就区间问题还算是比较典型的贪心题目，只能多做了，嫖个图在这。

![image.png](https://www.misaka19327.cc/static/img/e7611d3d6bf293254afac66a60dd808a.image.png)