题目链接

https://ac.nowcoder.com/acm/contest/9715/C

解题思路

找关系：

总共m个重音符，除去最左边的重音符还剩m-1个，我们确定最左边重音符的位置，计算此时剩下的m-1个重音符的位置关系有多少种：

1. 假设m-1=1，
   最左边的重音符偏移了0位，即如下图：此时，m-1个重音符的位置只能如图所示，即1种；
   最左边的重音符偏移了1位，即如下图：此时，m-1个重音符可以在标准位置不变也可以向前偏移一个位置，即蓝色圆形，即2种；
   最左边的重音符偏移了2位，即如下图：此时，m-1个重音符可以在标准位置不变也可以向前偏移一个位置，还可以偏移三个位置，即蓝色圆形，即3种；
   
2. 假设m-1=2，
   就有
   最左边的重音符偏移了0位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0；
   最左边的重音符偏移了1位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0，或者1，0，或者1，1；
   最左边的重音符偏移了2位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0，或者1，0，或者1，1，或者2，0，或者2，1，或者2，2；
   最左边的重音符偏移了3位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0，或者1，0，或者1，1，或者2，0，或者2，1，或者2，2，或者3，0，或者3，1，或者3，2，或者3，3；
   ……
3. 假设m-1=3，
   就有
   最左边的重音符偏移了0位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0，0；
   最左边的重音符偏移了1位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0，0，或者1，0，0，或者1，1，0，或者1，1，1；
   最左边的重音符偏移了2位，从左往右的m-1个重音符（不算最左边的）的偏移量顺次为0，0，0，或者1，0，0，或者1，1，0，或者1，1，1，或者2，0，0，或者2，1，0，或者2，1，1，或者2，2，0，或者2，2，1，或者2，2，2；
   ……
   这样一来我们可以列个表：
   

找到规律：
每个位置的值都等于它上一个和左一个的和，所以转移方程为 dp[i][j]=dp[i-1][j]+dp[i][j-1]
初始化：
dp[0][i]=1;

AC代码

const int N=1005;
const int MOD=1000000007;
int dp[N][N],ans;

class Solution {
public:
    /**
     * 
     * @param n int整型 乐谱总音符数
     * @param m int整型 重音符数
     * @param k int整型 重音符之间至少的间隔
     * @return long长整型
     */
    long long solve_bangbang(int n, int m, int k) {
        // write code here
        if(m==0) return 1;//！！！没有重音符的时候是1种情况

        for(int i=1;i<=n-(m-1)*(k+1);i++) dp[0][i]=1;//最大偏移量为n-(m-1)*(k+1)-1，i=1表示偏移量为0的情况

        for(int i=1;i<=m-1;i++)
        for(int j=1;j<=n-(m-1)*(k+1);j++)
        //for(int k=1;k<=j;k++)//<=> dp[i][j-1]
        //dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;    
        dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;

        for(int i=1;i<=n-(m-1)*(k+1);i++)//累加一下就是答案
        ans=(ans+dp[m-1][i])%MOD;

        return ans;
    }
};

个人总结

我裂开，居然找错转移方程了，而且找错误的转移方程也找了巨久……我是FW……