每日一题-整数划分

---

title: 每日一题–整数划分 date: 2019-10-27 17:15:16 tags:

算法每日一题

---

91.整数划分 (15分) C时间限制：2 毫秒 | C内存限制：65535 Kb 题目内容： 对于一个正整数n的划分，就是把n变成一系列正整数之和的表达式。注意，分划与顺序无关， 例如6=5+1跟6=1+5是同一种分划。另外，单独这个整数本身也算一种分划。 例如：对于正整数n=5，可以划分为： 1+1+1+1+1 1+1+1+2 1+1+3 1+2+2 2+3 1+4 5 输入描述 输入一个正整数n 输出描述 输出n整数划分的总数k 输入样例 5 输出样例 7

---

#include <stdio.h> int fun(int n, int m){ // 递归结束条件 if(n == 1 || m == 1){ return 1; }else if(n < 1 || m < 1){ return 0; }else if(n == m){ // 加上自己本身 + 0 这种组合情况 return fun(n, m - 1) + 1; }else if(n < m){ return fun(n, n); }else{ // 有m和无m两种情况 return fun(n - m, m) + fun(n, m - 1); } } int main(){ int n; scanf("%d", &n); printf("%d", fun(n, n)); return 0; }

---

递归思想，主要是确定结束条件，以及递归条件，所有情况都应该考虑到。