Ignatius and the Princess III(점진)
p[n][m]는 정수 n의 m를 n=x1+x2+x3+...+로 나눈다x;그 중에서 xi의 최대치는 m보다 작다.
그러면 문제를 어떻게 그 하위 문제로 전환시킬 것인가에 대해 토론해 봅시다.
1. m=1 또는 n=1일 때 분명히 dp[n][m]=1;
2. n
3.1 구분된 수에 m가 포함될 때 dp[n][m]=1;
3.2 구분된 수가 m를 포함하지 않을 때 문제는 정수 n의 m-1의 구분 dp[n][m]=dp[n][m-1]로 전환한다.
4、n>m일 때도 두 가지 상황으로 나뉜다
4.1 구분된 수에 m가 포함될 때 문제는 정수 n-m의 m로 구분 dp[n][m]=dp[n-m][m]로 전환한다.
4.2 구분된 수에 m가 포함되지 않을 때 문제는 정수 n의 m-1의 구분 dp[n][m]=dp[n][m-1]로 전환한다.
요약:
dp(n, m)= 1;(n=1 또는 m=1)
dp(n, n); (n
dp(n-m,m)+dp(n,m-1); (n>m)
직접 귀환은 시간을 초과할 수 있습니다. 그러면 우리는 기억화 검색의 방식으로 해결하거나 추이를 할 수 있습니다.
다음은 메모리 검색 코드입니다.
#include <stdio.h>
#include <string.h>
#define maxn 125
int dp[maxn][maxn];
int dfs(int n,int m)
{
int i,j;
if(dp[n][m]!=-1) return dp[n][m];
if(n==1 || m==1) return 1;
if(n<m) dp[n][m]=dfs(n,n);
else if(n==m) dp[n][m]=1+dfs(n,m-1);
else if(n>m) dp[n][m]=dfs(n-m,m)+dfs(n,m-1);
return dp[n][m];
}
int main()
{
int N,sum;
memset(dp,-1,sizeof(dp));
while(scanf("%d",&N)==1)
{
sum=dfs(N,N);
printf("%d
",sum);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
