(C++)白準2163チョコレートを切る


https://www.acmicpc.net/problem/2163
彼らは私たちに最小の割れ数を見つけさせた.
実際、どのように金を切るかによって切ると、最小限に切られます.
  • 式で表され、答えは(N−1)+N*(M−1)である.
  • DP展開を用いると、DP[N][M]=NxMサイズを1 x 1(最小)個に切り出す数を満たすテーブルを作成して
  • を展開することができる.
    #include <iostream>
    #include <cstring>
    using namespace std;
    
    int dpTable[302][302];
    
    int go(int n, int m){
    
        if(dpTable[n][m]!=-1) return dpTable[n][m];
        if(n==1) return dpTable[n][m] = m-1;
        if(m==1) return dpTable[n][m] = n-1;
    
        return dpTable[n][m] = go(1, m) + go(n-1, m) +1;
    }
    
    int main() {
    
        memset(dpTable, -1, sizeof(dpTable));
    
        int N,M;
        cin>>N>>M;
    
        cout<< go(N, M);
    
    
    }