（C++）昇順シーケンスを効率的に作成する方法（ダイナルソリューション）

Question

現在、昇順シーケンスを含むプログラムを作成しようとしています。 Nは、シーケンスの大きさであり、Kは、最大数、例えば

入力される：2,3-

出力：6（1,1 - 1,2 - 2,2 - 1,3 - 2,3 - 3,3）

私の現在のコードは正解を出力しますが、正解を得るには時間がかかります。これの最速のソリューションとはどのように私は動的なソリューションを行うのですか？ここでは遅いソリューションとのコードは次のとおりです。

#include<iostream> 
using namespace std; 
int n,k,cnt=0,mod=1000000007; 
int seq(int n, int k, int first, int depth){ 
    if(depth > n){ 
     cnt = cnt + 1; 
     return cnt; 
    } 
    else { 
     for(int i=first;i<=k;i++){ 
      seq(n,k,i,depth+1); 
     } 
    } 
    return cnt; 
} 
int main() 
{ 
    cin>>n>>k; 
    cout<<seq(n,k,1,1)%mod<<"\n"; 
    return 0; 
} 

Answer 1

私は動的プログラミングを使用してこの問題を解決しました。

#include<bits/stdc++.h> 
    #define up(j,k,i) for(i=j;i<k;i++) 
    #define down(j,k,i) for(i=j;i>k;i--) 
    #define pp(n) printf("%lld\n",n) 
    #define is(n) scanf("%lld",&n) 
    #define ips(n) scanf("%lld",n) 
    #define ss(s) scanf("%s",s) 
    #define cool 0 
    #define pb push_back 
    #define mp make_pair 
    #define F first 
    #define S second 
    #define f(i) cout<<i<<endl; 
    #define pll pair<lld,lld> 
    #define pi acos(-1) 
    #define ds(n,m) scanf("%lld %lld",&n,&m) 
    #define ts(n,m,k) scanf("%lld %lld %lld",&n,&m,&k) 
    typedef long double ld; 
    typedef long long int lld; 
    using namespace std; 
    const lld M =1e3+7; 
    const lld mod=1e9+7; 
    const lld infi =LLONG_MAX; 
    lld i,j,ans,k,n,x,y,m,mymax=LLONG_MIN,mymin=LLONG_MAX,b,c,z,sum; 
    lld dp[M][M],s[M][M]; 
    int main() 
    { 
     lld n,k; 
     ds(n,k); 
     up(1,k+1,i) 
     { 
     s[1][i]=1+s[1][i-1]; 
     } 
     up(2,n+1,i) 
     { 
     up(1,k+1,j) 
     { 
      s[i][j]=s[i][j-1]+s[i-1][j]; 

     } 
     } 
     pp(s[n][k]); 

      return 0; 
    } 

Answer 2

あなたは範囲1..Kで数Mから始めS(M)シーケンスを数えることができます。

は、あなたが非にするためにN同数M, M, M, M, M (N times)

のシーケンスを持っていることを想像し（そしてそれ以降のすべての数字）をインクリメントするのにL = 0..K-Mを使用することができます。たとえば、2つを使用すると、有効なシーケンスM, M, M+1, M+1, M+2を作成できます。

ので

S(M) = Sum{L=0..K-M} (C(L-1,N-1)) 

と

A(N, K) = Sum{M=1..K}(S(M)) 

これを行うには C(L-1, N-1)バリエーションがあることに注意してください（| | .. ..あなたは、L-1ドット間のN-1の垂直線...を挿入することができます）