6922. 将一个数字表示成幂的和的方案数
# 6922. 将一个数字表示成幂的和的方案数 (opens new window)
# 1.动规+二维背包问题
dp：第一个维度 i 代表可选的数字，第二个维度代表数字之和为 j 的方案数。
当前dp[ i][ j]更新时包含两部分：
- 考虑前 i-1种数字能够构成的方案数
- 选择第 i 个数字能够得到的方案数
class Solution {
public int numberOfWays(int n, int x) {
int[][] dp = new int[(int)Math.pow(n+1,(double)1/x)+1][n+1];
for(int i=1;i<dp.length;i++){
dp[i-1][0]=1;
for(int j=1;j<=n;j++){
if(j-(int)Math.pow(i,x)>=0) dp[i][j]=(dp[i][j]+dp[i-1][j-(int)Math.pow(i,x)])%1000000007;
dp[i][j]=(dp[i][j]+dp[i-1][j])%1000000007;
}
if((int)Math.pow(i+1,x)>n) return dp[i][n]%1000000007;
}
return -1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 2.动规+一维背包
上面dp数组迭代更新的过程中，当前状态 i 更新只和前一个数状态 i-1 的结果有关，只需要在考虑前 i-1 个数的方案数基础上加上当前第i个数能够组成的方案数即可。因此可以把二维dp简化成一维dp数组，但在时间复杂度上并没有减少。
注意：为了保证当前第 i 个数只能使用一次，遍历时需要从后往前遍历，更新时只会用到前面没有使用过的结果。否则从前往后遍历可能会使用上前面更新过的第i个数的方案数，出现重复使用的情况。
dp[j]+=dp[j-nums[i]];
1
# 3.记忆化搜索
原理：如果两个不同的节点搜索到达第index个索引时(深度为index的搜索树)，它们的当前数字之和都为sum，那么在往后搜索第index+1,index+2...层时，它们的搜索路径与行为是完全相同的。
记忆化Cache：使用搜索树层高+当前结果作为Map的key，作为区分相同搜索结果树节点的标志。保存以该节点为子树根的所有叶子节点传上来的结果和.
class Solution {
Map<String,Integer> map=new HashMap<>();
public int numberOfWays(int n, int x) {
int[] a = new int[(int) Math.pow(n+1, 1 / (double) x)+1];
for (int i = 1; i < a.length; i++) {
a[i]=(int) Math.pow(i,x);
}
return dfs(a, 1, 0,n);
}
public int dfs(int[] a, int index, int sum, int n) {
String str=String.valueOf(index)+","+String.valueOf(sum);
if(map.containsKey(str)) return map.get(str);
if(index==a.length){
map.put(str,sum==n?1:0);
return map.get(str);
}
int l=dfs(a,index+1,sum,n);
int r=dfs(a,index+1,sum+a[index],n);
map.put(str,l+r);
return map.get(str)%1000000007;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 背包问题
# 0-1背包
每个物品只能选择一次，因此当前第i个物品只有两种选择选或者不选，做完一次决策之后只能换下一种物品：
return dfs(nums,i+1,sum+value[i]) + dfs(nums,i+1,sum);
1
# 完全背包
每个物品可以选择多次，因此第i个物品可以选或者不选，选的话接下来还可以维持在第i个物品的状态：
return dfs(nums,i+1,sum) + dfs(nums,i,sum+value[i]);
1
对应动规数组更新时可以自前向后遍历。
# 多维背包
编辑 (opens new window)
上次更新: 2023/12/15, 15:49:57