2318.不同骰子序列的数目

本文主要是介绍2318.不同骰子序列的数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

经典的DP题目，求方案数 从序列中最后一个数字往前考虑 当前状态取决于前一个的状态和再前一个的状态所以dp（n，last，last1）为当前考虑的是第n个并且前一个数字是last 再前一个数字是last1的所有方案数，递归的边界是n==0 时候 返回1表示找到了一个合法的方案，我这里想说的是

DP其实记忆化的写法更加本质一些，更能体现它是一种暴力的手段

const int N = 1e4+10;
using ll = long long;
ll dp[N][10][10];
int mod = 1e9+7;ll dfs(int n,int last,int last1){if(n==0)return 1;if(~dp[n][last][last1])return dp[n][last][last1];ll res = 0;for(int i=1;i<=6;i++)if(i!=last&&i!=last1&&__gcd(i,last)==1)res = (res + dfs(n-1,i,last))%mod;return dp[n][last][last1] = res%mod;}class Solution {
public:int distinctSequences(int n) {memset(dp,-1,sizeof dp);return dfs(n,7,7);        }
};

这篇关于2318.不同骰子序列的数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---