练习1-递归与分治
铺砖
对于一个 2 行 N 列的走道。现在用 1×2,2×2 的砖去铺满。问有多少种不同的方式。
下图是一个 2 行 17 列的走道的某种铺法。
讲解视频：https://blog.csdn.net/Keven_11/article/details/119645827
算法思路：
主要还是一个拆分的思想，前两列的摆法无法拆解，所以事先定义，后面的摆法都可以拆解开来。
void solve(){
dp[1] = 1;
dp[2] = 3;
for(int i=3; i<=N; i++){
dp[i] = dp[i-1] + 2*dp[i-2]
}
}练习2-动态规划
最大连续子段和
给定有n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列连续的子段和的最大值。
例如，当(a1,a2,a3,a4,a5)=(-5,11,-4,13,-4-2)时，最大子段和为11+(-4)+13=20。
讲解视频：https://blog.csdn.net/p15008340649/article/details/115528578
算法思想：
用一等长的数组来存放当前的最大子段和，如果说当前最大子段和都小于0，那还不如不加当前元素，直接以当前元素开头；如果当前最大子段和大于0，那就加上当前元素，然后和最大值进行比较，取其中较大的值
void solve(){
int max = MIN_NUMBER; // 初始最大值设置为最小
dp[0] = a[0] // dp是用来存放当前最大子段和，其长度和给定序列长度一致
for(int i=1； i<n; i++){
if(dp[i-1]>0){
dp[i] = dp[i-1] + a[i]
}else{
dp[i] = a[i]
}
max = max(dp[i], max)
}
}练习3-贪心
减肥的小k1
小K没事干，他要搬砖头，为了达到较好的减肥效果，教练规定的方式很特别： 每一次，小K可以把两堆砖头合并到一起，消耗的体力等于两堆砖头的重量之和。
经过 n-1次合并后， 就只剩下一堆了。小K在搬砖头时总共消耗的体力等于每次合并所耗体力之和。小K为了偷懒，希望耗费的体力最小。
例如有 3堆砖头，数目依次为 1、2、9 。可以先将 1 、 2 堆合并，新堆数目为3 ，耗费体力为 3 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为12 。所以总共耗费体力 =3+12=15。可以证明 15为最小的体力耗费值。
算法思想：
消耗体力最小，那肯定每次合并的俩堆砖重量最小。
所以每合并一次需要将新产生的堆插入到合适位置
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int n, i;
int arr[1024] = {0};
int reslut = 0;
cin >> n;
for ( i = 0; i < n; i++){
cin >> arr[i];
}
// 排序
sort(arr, arr + n);
int tmp, k;
for ( i = 0; i < n - 1; i++) {
tmp = arr[i + 1] + arr[i];
k = i + 2;
while (arr[k] < tmp && k < n) {
arr[k - 1] = arr[k];
k++;
}
arr[k - 1] = tmp;
reslut += tmp;
}
cout << reslut << endl;
return 0;
}练习4-搜索
N皇后问题
n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互。给定一个整数n，返回n皇后不同的解决方案的数量。
补充知识：
皇后类似于象棋中的车，可以横着走、竖着走，同时他比车还高级点，可以以对角线的方式走，不管是主对角线还是副对角线
解题思路：
本题有一个很有意思的现象，和皇后所在同一主对角线上格子，其和相同；在同一副对角线上的格子，其差相同。例如（4，b）所在的副对角线有（3，a）、（5，c），俩元素的差为2。这是判断皇后是否可以摆放在改处的重要依据。
//a[row] = col：第row行的皇后摆放在第col列上
bool check(int x, int y){ //x行，y列，对应于调用时候的row，i
for(int row=1; row<=x; row++){ // 我们是一行一行去判断的，所以只需要考虑x之前的行
if(y == a[row]) return false; // 如果该列上有皇后摆放，则不能摆放
if(x+y == a[row] + row) return false; // 如果主对角线上有皇后，则不能摆放
if(x-y == row - a[row]) return false; // 如果副对角线上有皇后，则不能摆放
}
return true;
}
void dfs(row){ //row表示第row行
if(row==n+1){ //n表示n皇后，即有n行，n+1表示已经超出n行，搜索结束
result++; //此时已经产生一种情况，所以方案数加1
return;
}
for(int i=1; i<=n; i++){ //此处的i表示第i列，即第row行的皇后一列一列去判断是否可以在该处摆放
if(check(row, i)){ //此处的check()函数表示判断第row行的皇后能否在第i列摆放，如果可以，那将皇后摆放在改列，然后往下进行搜索
a[row] = i;
dfs(row+1);
a[row] = 0; //将第row的皇后归零
}
}
}