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);
}
};