逃离农场

//先用比较直观的做法，用三维数组保存每个状态
//dp[i][j][s]表示前i只牛选择j头，其和除以n的余数为s的个数
/*那么状态方程即：
当s>i:
dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - i];
当s<i:
dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][s - i + n];
综合一下
即为：
dp[i][j][s] = dp[i - 1][j][s] + dp[i - 1][j - 1][(s - i + n) % n];
*/

//这样就能解决这个问题，但是dp数组太大，超过内存限制，因此，使用滚动数组代替
#include<iostream>

using namespace std;

int dp[1005][55][1005] = { 0 };
int main()
{
	int n, k;
	//n = 7, k = 4;
	cin >> n >> k;
	int i, j, s;
	const int mod = 1000000007;
	dp[0][1][0] = 1;
	for (i = 1; i<n; i++)
	{
		dp[i][0][0] = 1;//初始条件设置好
		for (j = 1; j <= k; j++)
		{
			for (s = 0; s<n; s++)
			{
				dp[i][j][s] = (dp[i - 1][j][s] + dp[i - 1][j - 1][(s - i + n) % n]) % mod;
			}
		}
	}
	cout << dp[n - 1][k][0] << endl;
	system("pause");
	return 0;
}

//升级版
#include<iostream>

using namespace std;

int dp[2][55][1005] = { 0 };
void clear(int i)
{
	for(int j=0;j<55;j++)
		for(int s=0;s<1005;s++)
			dp[i][j][s]=0;
}
int main()
{
	int n, k;
	//n = 7, k = 4;
	cin >> n >> k;
	int i, j, s;
	const int mod = 1000000007;
	dp[0][1][0] = 1;
	for (i = 1; i<n; i++)
	{
		clear(i&1);
		dp[(i - 1) % 2][0][0] = 1;//初始条件设置好，缺少了这句，运行不正确，观察内存发现应该加这句
		for (j = 1; j <= k; j++)
		{
			for (s = 0; s<n; s++)
			{
				dp[i%2][j][s] = (dp[(i-1) % 2][j][s] + dp[(i - 1) % 2][j - 1][(s - i + n) % n]) % mod;
			}
		}
	}
	cout << dp[(i-1) % 2][k][0] << endl;
	system("pause");
	return 0;
}

//还可以继续优化，参考大佬的做法
//http://blog.csdn.net/sinat_33718563/article/details/74221986 //http://blog.csdn.net/xiaxzhou/article/details/73381206 //↑大佬的博客↑

//再升级版
#include <iostream>  
using namespace std;
const int modMin = 1e9 + 7;
int main()
{
	int dp[55][1005] = { 0 };//加上这句比较好
	dp[0][0] = 1;
	int n, k;
	while (cin >> n >> k)
	{
		for (int i = 0; i<n; i++)
		{
			for (int j = k; j >= 1; j--)
			{
				for (int s = 0; s<n; s++)
				{
					dp[j][s] = (dp[j][s] + dp[j - 1][(n + s - i) % n]) % modMin;
				}
			}
		}
		cout << dp[k][0] << endl;
	}
	return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int k = in.nextInt();
        final int MOD = 1000000007;

        int[][] dp = new int[k + 1][n];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = Math.min(k, i); j >= 1; j--) {
                for (int l = 0; l < n; l++) {
                    dp[j][l] = (dp[j][l] + dp[j - 1][(l + n - (i - 1)) % n]) % MOD;
                }
            }
        }

        System.out.println(dp[k][0]);
    }
}

import java.util.Scanner;
public class Main {
    private static final int mod = 1000_000_007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        System.out.println(escapeFarm(n, k));
    }

    /**
     * 从0~n-1的n个数中，取出k个
     * @param n n个数
     * @param k 取出k个
     * @return 组合数
     */
    public static int escapeFarm(int n, int k) {
        int[][] dp = new int[k+1][n]; //状态转移矩阵
        //初始赋值 ,i = 0时， 存在1个数，选出0个，余n为0,选出1个，余n为0，有1个
        dp[0][0] = dp[1][0] = 1;
        for (int i = 1; i < n; i++) {   //i 从1到n-1，算到n-1即为0~n-1中，选出k个数，其和余n为0
//            for (int j = 1; j <= Math.min(i+1, k); j++) {    //最少选1个数，最多选k个数
            for (int j = Math.min(i+1, k); j > 0; j--) {        //这个地方必须要倒序，因为j与j-1的值相关，即计算j时，j-1的值不能改变
                for (int l = 0; l < n; l++) {
                    dp[j][l] =(dp[j][l] + dp[j-1][(l-i+n)%n])%mod;
                }
            }
        }
        return dp[k][0];
    }
}