#include <iostream> using namespace std; //dp[i][j]表示第i种花位置,第j个位置为止 long long int dp[120][120]; long long int a[160]; int main() { int n,m; cin>>n>>m;//n种花m盆 for(int i=1;i<=n;i++){ cin>>a[i]; } dp[0][0]=1; for(int i=1;i<=n;i++ ){ for(int j=0;j<=m;j++){ for(int k=0;k<=j&&k<=a[i];k++){ dp[i][j]=(dp[i][j]+dp[i-1][j-k])%(1000007); } } } cout<<dp[n][m]; // 请在此输入您的代码 return 0; }
方法:二维动态规划
思路是:
利用一个数组dp[i][j]表示到第i种花第j个位置为止
花种的下标从1开始
dp[0][0]=1 -->到第0种花第0个位置初始化为1
核心代码:
for(int i=1;i<=n;i++ ){ for(int j=0;j<=m;j++){ for(int k=0;k<=j&&k<=a[i];k++){ dp[i][j]=(dp[i][j]+dp[i-1][j-k])%(1000007); } } }
花种的下标为1
遍历n种花,j个位置0~m(因为初始化dp[0][0]为1,dp[i-1][j-k]下标从[0][0]开始)
标签:摆花,下标,--,long,int,种花,dp From: https://www.cnblogs.com/luckyyaoyao/p/17977056