정수 구분 문제 귀속 최적화
7373 단어 귀속
n을 n보다 크지 않은 수 m로 나누려면
총 네 가지 상황으로 나뉜다
1. n==m이면 하나지만 계속 귀속해야 하기 때문에 1+q(n, m-1)와 같다
2. n
2.m 이하의 수로 계속 나누면 q(n, m-1)
3.그래서 합치면 q(n-m, m)+q(n, m-1)
4. 마지막으로 수출을 귀속시켰으니 밑바닥은 틀림없이 1이다
1 if(n==1 ||m==1)
2 return 1;전체 코드는 다음과 같다.
1 #include "stdio.h"
2 int q(int n,int m)
3 {
4 if(n==1 ||m==1)
5 return 1;
6 if(n<m)
7 return q(n,n);
8 if(n==m)
9 return 1+q(n,m-1);
10 if(n>m)
11 return q(n-m,m)+q(n,m-1);
12 }
13 main()
14 {
15 int n;
16 while(scanf("%d",&n)!=EOF)
17 {
18 printf("%d
",q(n,n));
19 }
20 } 넘치는 것을 피하려면 비교적 좋은 방법은 기억식의 귀속을 채택하는 것이다
즉, 매번 귀속이 끝난 후에 당신의 결과를 저장하고 다음 귀속이 끝날 때 바로 꺼내면 돼요. 더 이상 아래로 귀속되지 않아도 돼요.
1 #include "stdio.h"
2 int a[121][121];
3 int q(int n,int m)
4 {
5
6 if(n==1 ||m==1)
7 return a[n][m]=1;
8 if(n<m)
9 return q(n,n);
10 if(a[n][m]!=0)
11 return a[n][m];
12 if(n==m)
13 return a[n][m]=1+q(n,m-1);
14 if(n>m)
15 return a[n][m]=q(n-m,m)+q(n,m-1);
16 }
17 main()
18 {
19 int n;
20 while(scanf("%d",&n)!=EOF)
21 {
22 q(n,n);
23 printf("%d
",a[n][n]);
24 }
25 }좋은 웹페이지 즐겨찾기
