算法课作业

yirufeng

发布于：Dec 21, 2020

次浏览

八皇后问题：

回溯法

思路

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

代码

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的三步骤

状态的定义：dp[i][j] 表示字符串str1[0…i-1] -> str2[0…j-1]所需要的最小代价
找到状态转移方程：(画表来考虑状态转移方程，一共有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]的值
编码

代码

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)
}