4

我正在学习动态编程，并尝试使用动态编程解决Project Euler 的第 15 题。虽然我知道这个问题可以使用二项式系数来解决，但我想看看我学到了多少动态编程并因此尝试过。这是代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>

using namespace std;

int main()
{
    int gridsize;
    cin>>gridsize;


    int** grid = new int*[gridsize+1];
    for ( int i = 0; i < gridsize+1; i++) {
        grid[i] = new int[gridsize+1];
    }

    //Initialize the grid distances

    for ( int i = 1; i <= gridsize ; i++) {
        grid[i][0] = 1;
        grid[0][i] = 1;
    }
    grid[0][0] = 0;

    for ( int i = 1; i <= gridsize ; i++) {
        for ( int j = 1; j <= gridsize ; j++) {
            grid[i][j] = grid[i-1][j] + grid[i][j-1];
        }
    }
    cout<<grid[gridsize][gridsize]<<endl;
    delete(grid);   
    return 0;
}

预期的答案是 137846528820，而我得到的答案是 407575348。

4

3 回答 3

4

您的逻辑是相当正确的，问题是您遇到了整数溢出的情况。这是您的代码的修改版本，可以完美运行。只需将 更改int为long long unsigned类型。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>

using namespace std;
typedef unsigned long long ull;
int main()
{
    ull gridsize;
    cin>>gridsize;


    ull** grid = (ull**) malloc((gridsize+1)*sizeof(ull*));
    for ( int i = 0; i < gridsize+1; i++) {
        grid[i] = (ull*) malloc((gridsize +1)*sizeof(ull));
    }

    //Initialize the grid distances

    for ( int i = 1; i <= gridsize ; i++) {
        grid[i][0] = 1;
        grid[0][i] = 1;
    }
    grid[0][0] = 0;

    for ( int i = 1; i <= gridsize ; i++) {
        for ( int j = 1; j <= gridsize ; j++) {
            grid[i][j] = grid[i-1][j] + grid[i][j-1];
        }
    }
    cout<<grid[gridsize][gridsize];
    free(grid);
    return 0;
}
于 2012-06-07T06:59:18.600 回答
2

看来您溢出了int数据类型。根据计算：

137 846 528 820 模 (2^32) = 407 575 348

于 2012-06-07T07:01:20.513 回答
-2

电子表格似乎是一个方便的调试（或原始开发）工具：您可以按照您的算法快速构建一个来解决问题，它将在每个步骤中显示结果。这应该可以让您轻松识别网格右下方的溢出（从 grid[16][18] 开始）。

于 2012-06-23T17:53:34.823 回答