Algorithm8.6 数字类型题目整合
[TOC]
数字类型题目整合
数字题目类型整合：
- 若干个数相加组合成目标数的方案总和
- 小于等于4个数的平方的和组合成目标数的方案总和
- 给定一个数，问随意将这个数进行拆解，然后拆解得到的数做乘积，求乘积最大值
dfs转计数dp 问题1:若干个数相加组合成目标数的方案总和-可用dfs+剪枝出来
https://www.luogu.com.cn/problem/P1025
1、计数问题，dfs暴力搜
#include <iostream>
using namespace std;
#define maxtotal 205
#define maxn 8
int n, total, ans, dp[maxn][maxtotal];
void dfs(int last, int l, int val){
if (l == n) {
if (val == total) ans++;
return;
}
for (int i = last; val+i*(n-l)<=total; ++i) dfs(i, l+1, val+i);
}
int main() {
scanf("%d%d", &total, &n);
dfs(1, 0, 0);
printf("%d\n", ans);
return 0;
}
2、利用dp实现
确定dp数组以及没给维度的作用。dp[k][j]表示在第k个数且和为j的时候总方案数
状态转移方程为dp[k][j] += dp[k-1][j-i]
遍历的三个维度，分别为要算进去的数的数值i和要算进去的数的数量k和要填充的其他位置的dp数组的值
for (i ~ (1, M)) {
for (j ~ (i, M)) {
for (k ~ (1, n)) {
dp[k][j] += dp[k-1][j-i];
}
}
}
dfs转计数dp 问题2:小于等于4个数的平方的和组合成目标数的方案总和-需要用计数dp来实现
https://www.luogu.com.cn/problem/P1586
1、计数问题，dfs暴搜。(有使用剪枝，剪枝的思路就是搜索的话，允许当前数重复，但是不允许往前到倒着搜。所以把当前搜的这个数last往下传，到下一层的遍历就要在这层基础上进行搜索)
void dfs(int last, int l, int val) {
if (val == a) {ans++;return;}
if (l >= 4) return;
for (int i = last; i <= sqrt(a-val); ++i) dfs(i, l+1, val+i*i);
}
2、dp：通过确定了需要两给维度，选择的数的个数和当前所有选择的数的总和作为dp的两个维度=>
状态转移方程：dp[k][j] += dp[k-1][j-i*i]
确定了三个需要遍历的变量，所选择的数的数值区间范围i和选择的数的数量k和要求的总数
for (i*i ~ (0, m)) {
for (j ~ (i*i, m)) {
for (k ~ (1, 4)) {
// 对于dfs的转换就是把原来没有规则的搜索直接通过遍历，给提前算好了，摆在数组里，供使用
dp[k][j] += dp[k-1][j-i*i];
}
}
}