[Algorithm][综合训练][kotori和气球][体操队形][二叉树中的最大路径和]详细讲解

本文主要是介绍[Algorithm][综合训练][kotori和气球][体操队形][二叉树中的最大路径和]详细讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.kotori和气球

1.题目链接

kotori和气球

2.算法原理详解 && 代码实现

解法：数学 – 排列组合问题 -->

n * (n - 1)^{m - 1}

#include <iostream>
using namespace std;int main()
{const int MOD = 109;int n = 0, m = 0;cin >> n >> m;int ret = n;for(int i = 0; i < m - 1; i++){ret = ret * (n - 1) % MOD;}cout << ret << endl;return 0;
}

2.体操队形

1.题目链接

体操队形

2.算法原理详解 && 代码实现

解法：DFS + 枚举 --> 重点是画出决策树

#include <iostream>
#include <vector>
using namespace std;int n = 0, ret = 0;
vector<int> nums;
vector<bool> visit;void DFS(int pos)
{if(pos == n + 1){ret++;return;}// 对于该位置，依次枚举每个队员for(int i = 1; i <= n; i++){if(visit[i]) // 剪枝 -> i队员已经被放过{continue;}if(visit[nums[i]]) // 剪枝 -> i队员的诉求已经无法完成{return;}visit[i] = true; // 放上i号队员DFS(pos + 1);visit[i] = false; // 回溯}
}int main()
{cin >> n;nums.resize(n + 1, 0);visit.resize(n + 1, false);for(int i = 1; i <= n; i++){cin >> nums[i];}DFS(1); // 按进入位置划分cout << ret << endl;return 0;
}

3.二叉树中的最大路径和

1.题目链接

二叉树中的最大路径和

2.算法原理详解 && 代码实现

解法：DFS + 树形DP(后序遍历)

在某棵子树上整理什么信息：经过根节点的最大路径和
- ret = max(root->val + l + r, ret)
左子树提供：以左子树为根的最大单链和
- l = max(0, l)
右子树提供：以右子树为根的最大单链和
- r = max(0, r)
返回值：以自己为根的最大单链和
- return root->val + max(l, r);

class Solution
{
public:int ret = -0x3f3f3f3f;int maxPathSum(TreeNode* root) {DFS(root);return ret;}int DFS(TreeNode* root){if(root == nullptr){return 0;}// 左右子树最大单链和int l = max(0, DFS(root->left));int r = max(0, DFS(root->right));ret = max(ret, root->val + l + r); // 经过root的最⼤路径和return root->val + max(l, r);}
};