整数求和

题意：问从[1,n]中挑若干个数组成m的方案数，保证n,m <=120

思路：

  • 若n>m,dp[n][m]=dp[m-1][m]
  • 若n==m,dp[n][m]=dp[m-n][m]+1
  • 若n<m,考虑n是否在答案中dp[n][m]=dp[n-1][m-n] + dp[n-1][m]

复杂度:O(n*m)，其实也可以用滚动数组写，空间上是2*m

#include<bits/stdc++.h>
using namespace std;

int dp[200][200];

int main(){
    memset(dp,0,sizeof dp);
    int i,j;
    scanf("%d%d",&i,&j);
    for(int n=1;n<=i;n++){
        for(int m=1;m<=j;m++){
            if(n>m) dp[n][m]=dp[m][m];
            else if(n==m)   dp[n][m]=dp[m-1][m]+1;
            else    dp[n][m]=dp[n-1][m-n]+dp[n-1][m];
        }
    }
    printf("%d\n",dp[i][j]);

    return 0;
}