题目:建造房屋 (蓝桥OJ3362)

问题描述:

代码: 

#include<bits/stdc++.h>
using namespace std;
int n, m, k, ans, mod = 1e9 + 7;
long long dp[55][2605];
/*dp[i][j]：第i个街道上建j个房屋的总方案数
  枚举所有的转移，累加到dp[n][k]即总方案数
*/
int main()
{
	cin >> n >> m >> k;
	for(int i = 0; i <= k; i++)dp[0][i] = 1;  // 初始化，第一个街道上建造房屋的方案
	for(int i = 0; i < n; i++)  // 站在建好的前第i条街道上，去规划第i+1条街道怎么操作
		for(int j = 1; j <= m; j++)
			for(int l = i; l <= k; l++)
				(dp[i+1][j+l] += dp[i][l]) %= mod;	
	
  cout << dp[n][k] << '\n';	
	return 0;
}

知识点:动态规划