我正在解决这个问题 -> http://www.spoj.com/problems/SAMER08F/ (一个非常简单的问题)......我第一次去就得到了 AC......我的解决方案是这样的(非常简单):
#include<iostream>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
while(n!=0)
{
printf("%d",((n)*(n+1)*((2*n)+1))/6);
printf("\n");
scanf("%d",&n);
}
return 0;
}
我正在查看此列表 http://ahmed-aly.com/Category.jsp?ID=33我发现 Feynman 被列为 DP 问题......我是 DP 的初学者,无法弄清楚这个问题如何由子问题组成。寻找递归关系的任何帮助或提示都将非常有帮助。
最佳答案
这只是一个愚蠢的 DP。
你在这里做的是 对吧?
相反,你可以做的是创建一个数组来保存平方和(我们称之为 sumSquares)。现在,这就是您填充数组的方式:
总和[0] = 0; (基本情况,第一个的平方和 零元素为零)。
sumSquares[i] = sumSquares[i - 1] + (平方和 i 个元素的平方和是 (i - 1) 个元素的平方 + 第 个元素的平方和 元素)
就是这样!你迭代到 n,你的答案存储在 sumSquares[n] 中!
关于c++ - 如何在 SPOJ Feynman 中应用动态规划?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18117855/