c++ - 谁能解释一下我对欧拉项目 15 的动态规划方法有什么问题？

Question

我正在学习动态规划并尝试解决 Problem 15 of Project Euler使用动态规划。 虽然我知道这个问题可以使用二项式系数解决，但我想看看我学习了多少动态规划并尝试了多少。这是代码:

#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。

Answer 1

您的逻辑相当正确，问题是您遇到了整数溢出的情况。这是您的代码的修改版本，可以完美运行。只需将 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;
}