文章目录
- 一、题目描述
- 二、思路
- 三、代码
一、题目描述
https://www.luogu.com.cn/problem/P1077
题目描述很容易看懂
二、思路
动态规划题目,首先定义状态
dp[i][j]:摆前i种花,一共摆j盆的方案数。
i:1~n
j:1~m
需要注意的时,第i种花摆放的盆数范围是0~a[i].所以我们需要枚举 第
i种花 摆放多少盆。所以来一个三重循环。
状态转移方程:
k:1~a[i]&&k<m。dp[i][j]+=dp[i][j]+dp[i-1][j-k]
即在i,j确定的情况下,我们是需要枚举k,k为每次第i盆花放了k盆。
状态转移:第i盆花放了k盆,那么前i-1盆花就放了 j-k盆!
初始化:初始化个人感觉不是很容易,博主在这摔了跟头。因为我第一次的为dp[1][1]=1;一想感觉没什么问题。
但是dp[1][1]不一定等于1! 如果a[1]=0 的话 dp[1][1]就等于0了!!
所以初始化为 dp[0][0]=1 。从第一行i=1 而不再是i=2开始。
还要注意 取模1000007
滚动数组:
来一手滚动数组 将二维变一维。也就是覆盖 将这一行的值覆盖上一行。
对于滚动数组,我们就要思考 是正推还是逆推
状态转移时,对于每一行,我们都需要上一行前面的值,所以我们要逆推!
防止前面的值先被覆盖。
初始化 仍然dp[0]=1;
但是注意这里 k 一定要从1开始。
因为我们初始化时dp[0]=1的含义已经包含了 第i种花 一个也没选的情况
三、代码
#include <iostream>
#include <cstdio>
using namespace std;int main(){int n,m,a[105],dp[105][105]={0};scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&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<=a[i]&&k<=j;k++){dp[i][j]=(dp[i][j]+dp[i-1][j-k])%1000007;}}}printf("%d",dp[n][m]);return 0;
}
滚动数组:
#include <iostream>
#include <cstdio>
using namespace std;int main(){int n,m,a[105],dp[105]={0};scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);dp[0]=1;for(int i=1;i<=n;i++){//一定要逆推for(int j=m;j>=0;j--){for(int k=1;k<=a[i]&&k<=j;k++){dp[j]=(dp[j]+dp[j-k])%1000007;}}}printf("%d",dp[m]);return 0;
}