八皇后问题:

回溯法

思路

  1. 对于每一行有8个选择,
  2. 通过规则去掉不可以选择的,
  3. 对剩下可以选择的进行递归,递归达到结束条件就产生一种可能
  4. 撤销选择

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
package main

import (
"fmt"
)

/**
* @Author: yirufeng
* @Date: 2020/12/21 4:42 下午
* @Desc:
**/

//输入:N表示N行N列
//输出:一共有多少种摆放的方法
func process(n int) int {
if n <= 0 {
return 0
}
count := 0
record := make([]int, n)

var ret [][][]int
backtrack(0, n, &count, record, &ret)
showRet(&ret)
return count
}

func showRet(ret *[][][]int) {
fmt.Printf("-------------------------------一共有%d种解法-------------------------------\n", len(*ret))
for i := 0; i < len(*ret); i++ {
fmt.Printf("第%d种解法\n", i+1)
fmt.Println((*ret)[i])
}
}


func printToRet(ret *[][][]int, record []int) {
//初始化一个matrix
matrix := make([][]int, len(record))

for i := 0; i < len(record); i++ {
for j := 0; j < len(record); j++ {
if record[i] != j {
matrix[i] = append(matrix[i], 0)
} else {
matrix[i] = append(matrix[i], 1)
}
}
}

*ret = append(*ret, matrix)
}

//表示当前应该在第i行进行选择
func backtrack(i, n int, count *int, record []int, ret *[][][]int) {
//如果满足结束条件
if i == n {
//将结果打印到我们的ret中
printToRet(ret, record)
*count++
return
}

//做选择
for index := 0; index < n; index++ {
if isValid(record, i, index) { //判断在第i行的index列放置皇后是否和之前放置的冲突
record[i] = index
backtrack(i+1, n, count, record, ret)
record[i] = 0
}
}
}

//判断走的路径是否有效
//第一个参数record中的每一个元素表示对应行放置的皇后在第几列,例如record[0]=3表示第0行放置的皇后在第3列
func isValid(record []int, row, col int) bool {
//首先判断一下是否在该列上已经有了数字
for i := 0; i < row; i++ {
//说明该列长出现过该数字,或者没有出现过但是是对角线上的
if record[i] == col || abs(row, i) == abs(col, record[i]) {
return false
}
}
return true
}

func abs(a, b int) int {
if a > b {
return a - b
}
return b - a
}

func main() {
//使用8个皇后对应92种解法
process(8)
}

分治法

最小编辑代价

问题分析:

为何使用DP:发现有重叠子问题出现,考虑dp,因为满足最优子结构故可以使用dp

使用dp的三步骤

  1. 状态的定义:dp[i][j] 表示字符串str1[0…i-1] -> str2[0…j-1]所需要的最小代价
  2. 找到状态转移方程:(画表来考虑状态转移方程,一共有4种可能)
    2.1 如果dp[i-1][j-1] 且 str[i-1] == str2[j-1] ,那么dp[i][j] = dp[i-1][j-1]
    2.2 如果dp[i-1][j-1] 且 str[i-1] != str2[j-1] ,那么dp[i][j] = dp[i-1][j-1] + 替换的代价
    2.3 可以将str1[0..i-1] 先转换成 str2[0…j-2] ,然后再插入一个字符,将str2[0…j-2]转换成str2[0…j-1] 那么dp[i][j] = dp[i][j-1] + 插入的代价
    2.4 可以将str1[0…i-1] 先删除最后一个字符转换成 str1[0…i-2],然后转换成str2[0…j-1],那么dp[i][j] = dp[i-1][j] + 删除的代价
    2.5 取以上4种情况的最小值就是dp[i][j]的值
  3. 编码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package main

import "fmt"

/**
* @Author: yirufeng
* @Date: 2020/12/22 9:54 上午
* @Desc:
**/

//返回3个数的最小值
func min(a, b, c int) int {
var ret int
if a > b {
ret = b
} else {
ret = a
}

if ret > c {
ret = c
}
return ret
}


func minDistance(word1 string, word2 string) int {
//状态矩阵
dp := make([][]int, len(word1)+1)

for i := 0; i < len(dp); i++ {
dp[i] = make([]int, len(word2)+1)
}
//状态初始化
for i := 1; i < len(dp); i++ {
dp[i][0] = dp[i-1][0] + 1
}

for i := 1; i < len(dp[0]); i++ {
dp[0][i] = dp[0][i-1] + 1
}

cost := 0

//开始进行状态转移
for i := 1; i < len(dp); i++ {
for j := 1; j < len(dp[0]); j++ {
cost = 0
if word1[i-1] == word2[j-1] {
cost = dp[i-1][j-1]
} else {
cost = dp[i-1][j-1] + 1
}

dp[i][j] = min(cost, dp[i-1][j]+1, dp[i][j-1]+1)
}
}
ret := dp[len(dp)-1][len(dp[0])-1]
fmt.Printf("----------------------minDistance(%s -> %s):%d----------------------", word1, word2, ret)
return ret
}

func main() {
var str1, str2 string
fmt.Println("请输入第一个字符串:")
fmt.Scanln(&str1)
fmt.Println("请输入第二个字符串:")
fmt.Scanln(&str2)
minDistance(str1, str2)
}

图着色

  1. EDSCsb
  2. BRn0Y7
  3. 0z5Dce
  4. f7S9Mi
  5. 7BHYq7
  6. lBwqmk
  7. RWRxeB
  8. WG85an
  9. NS6dbl
  10. zBYvTZ
  11. UpcYZU

评论