解法:数学 – 排列组合问题 --> n ∗ ( n − 1 ) m − 1 n * (n - 1)^{m - 1} n∗(n−1)m−1
#include<iostream>usingnamespace std;intmain(){constint 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;return0;}
2.体操队形
1.题目链接
体操队形
2.算法原理详解 && 代码实现
解法:DFS + 枚举 --> 重点是画出决策树
#include<iostream>#include<vector>usingnamespace std;int n =0, ret =0;
vector<int> nums;
vector<bool> visit;voidDFS(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;// 回溯}}intmain(){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;return0;}
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);
classSolution{public:int ret =-0x3f3f3f3f;intmaxPathSum(TreeNode* root){DFS(root);return ret;}intDFS(TreeNode* root){if(root ==nullptr){return0;}// 左右子树最大单链和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);}};