hihoCoder #1444 : Push Button II ( dp

题目链接:
https://hihocoder.com/problemset/problem/1444

题意:

很容易发现这个就是一个线性的$dp$
考虑一下 $dp[i][j]$表示长度$i$的分为$j$大小的块的大学长度
明显我们可以发现 状态$dp[i][j]$的状态可以由$dp[i][j-1]$和$dp[i-1][j-1]]$推出来 ,所以状态转移方程为
$dp[i][j]=dp[i-1][j-1]\ast j+dp[i][j-1]\ast j$

//    Created by Yishui
//    Time on 2018/10/
//    E-mail: Yishui_wyb@outlook/*---------------------------------*/#include 
using namespace std;#define cpp_io() {ios::sync_with_stdio(false); cin.tie(NULL);}
#define rep(i,a,n) for (int i=a;i
#define repp(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define CLR(a,b) memset(a,(b),sizeof(a))
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ls o<<1
#define rs o<<1|1typedef long long ll;
typedef vector<int> VI;
const int MAXN = (int)1e3+10;
const int INF = 0x3f3f3f3f;
const int mod = (int)1e9+7;void F() {
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endif
}ll dp[MAXN][MAXN];int main() {int n; cin>>n;dp[0][0]=1;repp(i,1,n) repp(j,1,n) {dp[i][j] = dp[i-1][j-1]*j*1LL+dp[i-1][j]*j*1LL;dp[i][j]%=mod;}ll ans=0;repp(i,1,n) ans=(ans+dp[n][i])%mod;cout<<ans<<"\n";return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！