前言
今天的三个题目分别是：WY22 Fibonacci数列、NC242 单词搜索、BC140 杨辉三角。
1. Fibonacci数列
1.1 题目描述
1.2 解题思路
一道非常简单的dp问题，甚至连动态转移方程都给给出了。状态表示就是：到达第n个位置，F[n]的值为多少，状态转移方程就是：F[i] = F[i-1] + F[i-2]。 因此用一个for循环就可以解决问题了。然后找到第一个大于n的数，将n与第一个大于它的数和第一个小于它的数进行比较，算出差值就可以了。
1.3 代码实现
#include <iostream>
using namespace std;
#include <vector>
int main()
{
int n = 0;
cin >> n;
vector<int> dp(1000, 0);
int ret = 0x3f3f3f3f;
dp[0] = 0, dp[1] = 1;
for (int i = 2; dp[i - 1] < 1e6 + 1; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
if (n <= dp[i])
{
ret = min(ret, dp[i] - n);
ret = min(ret, n - dp[i - 1]);
break;
}
}
cout << ret;
return 0;
}
2. 单词搜索
2.1 题目描述
2.2 解题思路
这是一道典型的dfs（深度优先搜索）的题目，实际上也就是暴力搜索，将每一个格子当作起点，再将其余格子当成第二步，……，也就是将所有情况都枚举出来，看看有没有符合条件的路径。
2.3 代码实现
class Solution {
public:
int m, n;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool vis[101][101];
bool dfs(vector<string>& board, string word, int i, int j, int pos)
{
vis[i][j] = true;
if (board[i][j] != word[pos])
{
return false;
} else
{
if (pos == word.size() - 1) return true;
if (board[i][j] == word[pos])
{
for (int k = 0; k < 4; k++)
{
int x = i + dx[k], y = j + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y])
{
if (dfs(board, word, x, y, pos + 1)) return true;
vis[x][y] = false;
}
}
}
}
return false;
}
bool exist(vector<string>& board, string word)
{
memset(vis, 0, sizeof vis);
m = board.size(), n = board[0].size();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
{
if (dfs(board, word, i, j, 0)) return true;
vis[i][j] = false;
}
return false;
}
};
3. 杨辉三角
3.1 题目描述
3.2 解题思路
这一道题也是一道基础的dp问题，照着题目描述进行模拟即可，状态表示和状态状态转移方程都已经给出了，这就相当于一道模拟题了。不过需要注意的是，答案要求输出域宽为5，也很简单，大家看代码即可。（用C语言的printf）文章来源：https://www.toymoban.com/news/detail-856338.html
3.3 代码实现
#include <iostream>
using namespace std;
#include <vector>
int main()
{
int n = 0;
cin >> n;
vector<vector<int>> nums(n, vector<int>(n, 0));
for (int i = 0; i < n; i++)
{
nums[i][0] = nums[i][i] = 1;
for (int j = 1; j <= i; j++)
{
nums[i][j] = nums[i - 1][j] + nums[i - 1][j - 1];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
printf("%5d", nums[i][j]);
}
cout << endl;
}
return 0;
}
总结
今天的第一题和第三题都比较简单，就是两道模拟题，第二道题稍微有些难度，但是只要学会了dfs，相信不成问题。我上面写的dfs就是一个比较基础的模板，可以套用大部分的dfs题目，如果有不会的小伙伴，可以私信我，之后会出一期专门的文章来进行讲解。
那么第三天的内容就到此结束了，如果大家发现有什么错误的地方，可以私信或者评论区指出喔。我会继续坚持训练的，共勉！！！那么本期就到此结束，让我们下期再见！！觉得不错可以点个赞以示鼓励！文章来源地址https://www.toymoban.com/news/detail-856338.html
到了这里，关于强化训练：day3的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
