c++ - 如何在SPOJ Feynman中应用动态编程？

我正在解决这个问题-> 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)。现在，这是填充数组的方式:

sumSquares [0] = 0; (基本情况，第一个的平方和
零元素就是零)。

sumSquares [i] = sumSquares [i-1] +(平方和
第i个元素是(i-1)个元素的平方和第ith个平方的和
元素)

就是这样!您迭代到n，然后将答案存储在sumSquares [n]中!

关于c++ - 如何在SPOJ Feynman中应用动态编程？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18117855/