P76038 骰子拼出目标 — 题解

专题： 动态规划
适用题目： 新生 OJ 本地题包中的 P76038，不要直接用于外站同名题。

解题思路

设 f[i] 为拼出和 i 的方案数，最后一次掷骰点数为 1～6，得到 f[i]=sum(f[i-j])。

复杂度

时间 $O(6n)$，空间 $O(n)$。

易错点

顺序不同算不同方案；初始状态 f[0]=1。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    int n;scanf("%d",&n);const int mod=1000000007;
    int *f=calloc(n+1,sizeof(int));f[0]=1;
    for(int i=1;i<=n;i++)for(int j=1;j<=6 && j<=i;j++){
        f[i]+=f[i-j];if(f[i]>=mod)f[i]-=mod;
    }
    printf("%d\n",f[n]);free(f);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    const int mod=1000000007;
    vector<int>f(n+1);
    f[0]=1;
    for(int i=1;i<=n;i++)for(int k=1;k<=6&&i-k>=0;k++){
        f[i]+=f[i-k];
        if(f[i]>=mod)f[i]-=mod;
    }
    cout<<f[n]<<nl;
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。