n을 최대 수가 m를 초과하지 않는 수로 나누다

이전에 비슷한 글을 썼는데 오늘은 n을 m보다 크지 않은 종수로 나누는 또 다른 방법을 보았다.
여러 정수를 나누면 같은 정수가 존재할 수 있습니다.
dp[n][m]=dp[n][m-1]+dp[n-m][m]dp[n][m]는 정수 n의 구분에서 매 수가 m의 구분수보다 크지 않다는 것을 나타낸다.구분수는 두 가지 상황으로 나눌 수 있다. a. 구분에서 각 수는 m보다 작고 각 수는 m-1보다 크지 않기 때문에 구분 점수는 dp[n][m-1]이다.b. 구분 중 하나가 m이다. 그러면 n에서 m를 빼고 나머지는 n-m를 구분하는 것과 같기 때문에 구분 점수는 dp[n-m][m]이다.
여러 개의 다른 정수를 나누는 경우:
dp[n][m]=dp[n][m-1]+dp[n-m][m-1]dp[n][m]는 정수 n의 구분에서 매 수가 m의 구분수보다 크지 않다는 것을 나타낸다.같은 구분 상황은 두 가지 상황으로 나뉜다. a. 구분 중의 각 수는 m보다 작고 각 수는 m-1보다 크지 않으며 구분 수는 dp[n][m-1]이다.b. 구분 중 하나는 m이다. n에서 m를 빼고 나머지는 n-m를 상당히 구분한다. 그리고 매 수는 m-1보다 크지 않기 때문에 구분 점수는 dp[n-m][m-1]이다.

#include 
using namespace std;

int getNum( int n, int m )
{
    if( 1 == n || 1 == m )
        return 1;
    if( n <= m )
        return getNum( n, n - 1 ) + 1;
    else
        return getNum( n, m - 1 ) + getNum( n - m, m );
}

void main()
{
    int n, m;
    cin >> n >> m;
    cout << getNum( n, m ) << endl;
}

예제: 출처계 마늘꾼
구분수는 정수 nn을 00보다 큰 몇 개의 합으로 나누는 것이다.예를 들어 n=4n=4는 1+1+1+11+1+1+1, 1+1+21+1+2, 1+31+3, 2+22+2, 44로 나눌 수 있는데 모두 55가지 방안이 있는데 1+1+21+1+2, 1+2+11+2+1, 2+12+11은 같은 방안으로 여겨진다.
정수 8080의 구분수 방안을 구하다.
ffs는 코드를 붙이지 않고 dp를 사용했다. dp[n][k]는 수 n을 k로 나누고 dp[n][k]=dp[n-1][k-1]+dp[n-k][k]는 1과 1로 나눈다.

#include
using namespace std;
int dp[100][100];
int main()
{
	int n;
	cin>>n;
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
		dp[i][0]=0;
	for(int i=1;i