返回信息流每发子弹命中环数为1-10内，现有10发子弹，最后打靶结果为90环的打法可能性有多少种？要求使用递归实现。
递归学的不好，希望解答，谢谢！
这是一条镜像帖。来源：北邮人论坛 / cpp / #29180同步于 2009/9/27
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
求教一个递归实现的问题
chensiever
2009/9/27镜像同步10 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
f[10][90]=f[9][89]+f[9][88]+...+f[9][80]
...
f[i][j]=f[i-1][j-1]+f[i-1][j-2]+...+f[i-1][j-10]
DP了
【 在 xieys (枫叶/兄弟会堂主/借楼同征外援) 的大作中提到: 】
: f[10][90]=f[9][89]+f[9][88]+...+f[9][80]
: ...
: f[i][j]=f[i-1][j-1]+f[i-1][j-2]+...+f[i-1][j-10]
: ...................
long long f(int i, int j)
{
if (i == j) return 1;
if (i > j) return 0;
if (i == 1)
{
if (j >= 1 && j <= 10) return 1;
else return 0;
}
long long sum = 0;
for (int k = 1; k <= 10 && j - k >= 1; k ++)
{
sum += f(i - 1, j - k);
}
return sum;
}
dp和递归是相通的
【 在 IceTea 的大作中提到: 】
: DP了
如果这样记忆的递归,那就快多了
#include <stdio.h>
long long ans[100][1000];
long long f(int i, int j)
{
if (ans[i][j] >= 0) return ans[i][j];
if (i == j) return ans[i][j] =1;
if (i > j) return ans[i][j] = 0;
if (i == 1)
{
if (j >= 1 && j <= 10) return ans[i][j] = 1;
else return ans[i][j] = 0;
}
long long sum = 0;
for (int k = 1; k <= 10 && j - k >= 1; k ++)
{
sum += f(i - 1, j - k);
}
return ans[i][j] = sum;
}
int main()
{
memset(ans, -1, sizeof(ans));
printf("%lld\n", f[10][90]);
return 0;
}
赞~记忆化递归王道
【 在 xieys 的大作中提到: 】
: 如果这样记忆的递归,那就快多了
: #include <stdio.h>
: long long ans[100][1000];
: ...................
是动态规划么,这两天逛论坛见了好几次这个,能解释下这个表达式不,sb了,答案出来还不开窍,攒恢复速度和能力
【 在 xieys 的大作中提到: 】
: f[10][90]=f[9][89]+f[9][88]+...+f[9][80]
: ...
: f[i][j]=f[i-1][j-1]+f[i-1][j-2]+...+f[i-1][j-10]
f[i][j]表示打i次得j分的情况
如果第i枪打的是1,那么其余i-1枪有f[i-1][j-1]种可能
......................2,.....................f[i-1][j-2]
.
.
.
......................10,....................f[i-1][j-10]
【 在 chensiever 的大作中提到: 】
: 是动态规划么,这两天逛论坛见了好几次这个,能解释下这个表达式不,sb了,答案出来还不开窍,攒恢复速度和能力