回溯算法
輸入 一個(gè)數(shù)n
數(shù)組結(jié)果集
例如：
輸入一個(gè)值為
6
結(jié)果為
6
5 1
4 2
4 1 1
3 3
3 2 1
3 1 1 1
2 2 2
2 2 1 1
2 1 1 1 1
1 1 1 1 1 1
本題使用全排列的方式計(jì)算結(jié)果
@Test
public void teset() {
List<String> strings = generateTogether(6);
strings.forEach(System.out::println);
}
public List<String> generateTogether(int n) {
List<String> res = new ArrayList<>();
generate(res, "", n, n);
return res;
}
//max 表示后面的i的最大值，i對(duì)應(yīng)的后面為相加的值
private void generate(List<String> res, String ans, int max, int i) {
if (i == 0){
res.add(ans);
return;
}
for (int j = i; j > 0; j--) {
if (max >= j) {
generate(res, ans +" "+ j,j,i-j);
}
}
}
本題擴(kuò)展
計(jì)算有多少種結(jié)果
例如 上題中 6 的結(jié)果又11
1 結(jié)果為1
2的結(jié)果為2
3的結(jié)果為3
本題采用動(dòng)態(tài)規(guī)劃的方法
思路
| 0 | 1 | 2 | …… | n | |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | …… | 1 |
| 2 | 1 | 1 | 2 | …… | dp[n]+=dp[n-2] |
| …… | …… | …… | …… | …… | …… |
| n | dp[0] | dp[1] | dp[2] | …… | dp[n]+dp[0] |
private long printResult(int n) {
int dp[] = new int[n + 1];
Arrays.fill(dp, 1);
for (int i = 2; i <= n; i++) {
for (int j = i; j <= n; j++) {
dp[j] += dp[j - i];
}
}
return dp[n];
}
