# 1、课程设计题目汇总表
| 序号 | 题目 |
| :----------: | :---------------------------- |
| **Base** | **基础题目** |
| 1 | 最长回文子序列 |
| 2 | 最长递增子序列 |
| 3 | 最长等差子序列 |
| 4 | 最长公共子序列 |
| 5 | 最优编辑距离 |
| **LeetCode** | **选做题目** |
| 6 | #分治# 构建平衡二叉树 |
| 7 | #分治# ==合并 K 个升序序列== |
| 8 | #贪心# ==分发糖果== |
| 9 | #贪心# 吃苹果的个数 |
| 10 | #DP# ==连接词== |
| 11 | #DP# 打家劫舍 |
| 12 | #回溯# ==完成所有工作的时间== |
| 13 | #回溯# 全排列 |
# 2、主要内容
## 2.1、最长回文子序列
### 2.1.1、题目描述
> 给你一个字符串 s,找出其中最长的回文子序列,并返回该序列的长度。
>
> 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。
>
**标签**:==动态规划== >> 区间 DP
### 2.1.2、程序使用方式说明
1. **实机环境说明**:
- **OS**: macOS 11.6 20G165 x86_64
- **Kernel**: Darwin 20.6.0 Mon Aug 30 06:12:21 PDT 2021;
2. **go env**
已自动略去不相关部分。
```bash
GO111MODULE="on"
GOARCH="amd64"
GOOS="darwin"
GOPROXY="https://goproxy.cn,direct"
GOROOT="/Users/evlic/SDK/Go/go1.17.5"
```
> **ps**:上述两项环境说明将不再重复展示, 之后的「程序使用方式说明」将仅展示程序启动相关描述,以及必要描述。
在具有 go 环境的设备上,切换到源码根目录执行 `go mod tidy`,即可完成依赖导入。
**依赖声明**:本项目仅使用必要的图形化或用于实现 web 接口的 http 支持库、日志库以及 Golang 内置标准库,算法实现部分均由本人完成代码编写。
3. **程序启动**
本题源码位于 ACD/base/no_01下,包内 `base_test.go` 文件为编写好的测试类。
请确保终端位于==**源码目录**==下执行
- **内置数据的测试**
- ```go
go test -v ACD/base/no_01 -test.run TestByBuiltinData
```
- **命令行输入参数**
- ```go
go test -v ACD/base/no_01 -test.run TestByStdin -args xxx1 xxsxs1 dsds2
```
- 参数 `-args` 后可以跟任意字符串,空格作为分界线。
### 2.1.3、分析与设计
- **算法分析**
- 回文串子序列问题,很适合使用动态规划求解。因为动态规划可以自底向上求解问题,本题中的回文条件就有一个很简单的起始状态,len = 1,必定是回文串。
- 动态规划本质是带记事本记录中间状态的暴力枚举法,本题中各个中间状态的回文子序列可以用动态规划很好的记录,并避免(相比其他算法思想)重复搜索。
- **DP 要素解释**
- 1、 ==dp 数组以及下标的定义==
- 定义 `dp[n][n]` 数组
- `dp[i][j]` 表示字符 `s` 在区间 `[i...j]` 的最大回文序列长度
- 2、状态转移方程
- 每一步 `i`、`j` 更改的时候,比较 `s[i] 与 s[j]`
- **相等**: `s[i]、s[j]` 均加入最长回文子序列中
- $dp[i][j]=dp[i+1][j-1] + 2$
- **else**:意味着`s[i]、s[j]` 不能全部加入最长回文子序列中
- 判断一下==三种情况==,并取最大值
- 只有 `s[i]` 加入
- $dp[i][j]=dp[i+1][j] + 1$
- 只有 `s[j]` 加入
- $dp[i][j]=dp[i][j - 1] + 1$
- 均不加入
- $dp[i][j]=dp[i+1][j - 1]$
- 3、**初始化**
- 对==边界情况==考虑
- 当 `i = j`成立时,字符串长度为 1
- 此时形成回文串长度为 1
- 根据 ==状态转移方程== 考虑,此时 `s[i]、s[j]` 下标相同,
将执行 $dp[i][j]=dp[i+1][j-1] + 2$
这是不符合 ==dp数组 定义==的情况
(取区间 `[i...j]`,是认为 `i <= j 成立的`)
- 所以,初始化时:将所有 `dp[i][i]` 赋值为 1
- 4、**遍历顺序**
- 分析状态转移方程
$$dp[i][j]= \begin{cases} dp[{{i+1}}][j-1] + 2, & s[i] == s[j] \\ \\ max\Bigg( \begin{aligned} dp[{{i+1}}][j] + 1\\ \\ dp[i][{{j - 1}}] + 1 \\ \\dp[{{i+1}}][j - 1] \end{aligned} \Bigg) & s[i] != s[j] \end{cases}$$
- 不难发现状态转移过程中 `dp[][]` 数组非常依赖 ==下一行== `dp[i+1][]` 的状态
- 所以数组的垂直遍历顺序应该从==下到上==,即 `i` 从 `n - 1` 到 `0`
- `j` 顺序遍历 且 `j > i`, 即 `j` 从 `i + 1` 到 `n - 1`
- 这样的遍历顺序才可以支撑状态转移方程的成立。
- **伪代码**
```lua
// 输入字符串
// 输出最长回文子序列
算法 longestPalindromeSubseq(s string) int
n = len(s)
dp=[[],...,[]] // n * n
// 初始化
for i <- 0 to n - 1 do {
dp[i][i] = 1
}
for i <- n - 1 to 0 do {
for j <- i + 1 to n - 1 do {
if s[i] == s[j] {
dp[i][j] = dp[i + 1][j - 1] + 2
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
}
}
}
return dp[0][n - 1]
```
- **算法复杂度分析**
本题可以分两部分讨论算法复杂度
- 初始化:
- 时间复杂度 $O(n)$
- 空间复杂度 $O(n^2)$
- 状态转移:
- 时间复杂度 $O(n^2)$
- 空间复杂度 $O(1)$
所以本题算法复杂度为:这种实现方法 最好情况 和 最坏情况 复杂度相同
- 空间复杂度 $O(n^2)$
- 时间复杂度 $O(n^2)$
### 2.1.4、测试用例
| 测试用例编号 | 程序输入以及步骤 | 期待结果(输出) | 实际结果(输出) | 是否通过 |
| ------------ | ------------------------- | ---------------- | ---------------- | -------- |
| 1 | "bbbab" | 4 | 4 | 通过 |
| 2 | "cbbd" | 2 | 2 | 通过 |
| 3 | "xxxxx22xxxs4aossd2xxxxx" | 15 | 15 | 通过 |
- **Go-testing**![](https://www.writebug.com/myres/static/uploads/2022/4/1/8ce6ff0a1bf2ce4592c17aa4a14a71f5.writebug)
- **LeetCode AC**
![](https://www.writebug.com/myres/static/uploads/2022/4/1/312833344a54f7ffffc3cfa492f05d58.writebug)
---
## 2.2、最长递增子序列
### 2.2.1、题目描述
> **题目**
>
>
>
> 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
>
> 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
**标签:**#动态规划# ==#中等#==
### 2.2.2、程序使用方式说明
**程序启动**
- **程序启动**
- 内置数据的测试方法
```go
go test -v ACD/base/no_02 -test.run TestByBuiltinData
```
- 命令行参数方式的输入方法
```go
go test -v ACD/base/no_02 -test.run TestByStdin -args 1 3 2 5 6 7
```
### 2.2.3、分析与设计
- 动态规划
- 定义: `dp[i]` 表示 选择第 `i` 号 元素后,最长递增子序列长度
- 递归公式:$dp[i] = max(dp[0...i - 1] )+ 1 $
- 初始化:
- dp数组,表示 第 i 个元素对应的最大递增子序列,初始值应该填充为 1
- ans,初始化为 1
- 边界条件:
- len == 0,直接返回 0
- 否则返回 ans,每次成功计算 dp[i] 后, 更新 ans
- 遍历顺序
- 从递推公式可知,可以从 前向后遍历。
- 伪代码
- ```lua
--
没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
收起资源包目录
100011975-基于GO语言进行算法课程设计.zip (42个子文件)
algorithm_course_design
go.mod 133B
go.sum 899B
LICENSE 1KB
算法课设·要求.md 4KB
.idea
git_toolbox_prj.xml 507B
.name 12B
codeStyles
codeStyleConfig.xml 149B
vcs.xml 180B
misc.xml 172B
modules.xml 264B
.gitignore 194B
base
no_05
minD_test.go 1KB
minDistance.go 522B
no_04
longestCommonSubsequence.go 393B
lcss_test.go 1KB
no_01
base_test.go 907B
longest_palindromic_subsequence.go 784B
no_02
lengthOfLIS.go 474B
LIS_test.go 1KB
no_03
lss_test.go 1KB
longestSubsequence.go 614B
common
common.go 1KB
算法课设·文档·初定稿.md 72KB
算法课设.iml 337B
leetcode
no_07
mkl_test.go 1KB
mergaKLists.go 920B
no_13
permute.go 423B
permute_test.go 2KB
no_06
constructMaximumBinaryTree.go 566B
cmb_test.go 1KB
no_11
rob.go 358B
rob_test.go 1KB
no_08
candy.go 502B
candy_test.go 1KB
no_09
eA_test.go 858B
eatenApple.go 1KB
no_10
facwad_test.go 1KB
findAllConcatenatedWordsInADict.go 1007B
no_12
mmtr_test.go 2KB
minimumTimeRequired.go 851B
README.md 46KB
算法课设·文档·导出打印稿.md 47KB
共 42 条
- 1
资源评论
神仙别闹
- 粉丝: 2687
- 资源: 7649
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功