【dfs|LightOJ1030-Discovering Gold-dp】题目大意：有n个点，开始在1这个点，每次用筛子前进，每到达一个新的点，就把当前的点的金子收下，如果那个点>n就返回去重新抛，问你最后金子的期望是多少；
题目解析：概率dp，一开始一直想着从前面开始dp，肯定不可以因为时间复杂度太高，应该从后面开始dp，这样就是记忆化搜索了，时间复杂度会大大降低；
AC代码：
#include
#include
#include
#include
#include
using namespace std;
double dp[110];
int a[110],n;
double dfs(int pos)
{
if(dp[pos]!=-1.0)
return dp[pos];
int i,cnt=0;
double ans=0;
for(i=1;
i<=6;
i++)
{
if(pos+i<=n)
{
cnt++;
ans+=dfs(pos+i);
}
}
dp[pos]=ans*(1.0/cnt)+a[pos];
return dp[pos];
}
int main()
{
int cas,c,i;
scanf("%d",&cas);
for(c=1;
c<=cas;
c++)
{
scanf("%d",&n);
for(i=1;
i<=n;
i++)
{
scanf("%d",&a[i]);
}
for(i=1;
i<=n;
i++)
dp[i]=-1.0;
dp[n]=a[n];
printf("Case %d: %.12lf\n",c,dfs(1));
}
return 0;
} 推荐阅读
- dfs|数独游戏dfs
- 动态规划|符环 解题笔记
- #|蓝桥杯31天冲刺打卡题解（Day3）
- 安卓|安卓适配AutoSize详解
- 数据机构与算法|找规律之动态规划系列
- 遇见蓝桥遇见你|小唐开始刷蓝桥（一）2020年第十一届C/C++ B组第二场蓝桥杯省赛真题