C程序-动态规划算法中奇怪的段错误

Question

我正在用 C 语言编写一个程序来执行一个简单的动态编程算法，您可以在其中返回加起来达到一定数量所需的最少硬币数量。这是我的代码:

#include <limits.h>
#include <stdlib.h>
#include <stdio.h>

/*
This function returns the minimum number of stamps required for a given value.
It assumes that the given array contains the available stamp sizes, and that it
always contains 1, so a solution is always possible
*/
int min_number_of_stamps(const int* array, size_t array_size, int request) {

    /* Construct a table with dimensions (array_size+1)*(request+1) */ 
    int numRows = array_size + 1;
    int numCols = request + 1;
    int **DPtable; 
    DPtable = malloc(numRows*sizeof(int));
    int i;
    for (i = 0; i < numRows; i++) {
        DPtable[i] = malloc(numCols*sizeof(int));
    }
    printf("%d",DPtable[4][0]);
    int r, c, useIt, loseIt;
    for (r = 0; r < numRows; r++) {
        for (c = 0; c < numCols; c++) {
            printf("%d,%d\n", r, c);
            if (c==0) {
                printf("1\n");
                //if the amount of change is 0, 0 coins are needed 
                DPtable[r][c] = 0;
            } 
            else if ((r==0) || c < array[r-1]) {
                printf("2\n");
                //if there are no coins or if the change needed is less than 
                //the smallest coin available, then 'infinity' coins are needed
                DPtable[r][c] = INT_MAX;
            } 
            else { 
                printf("3\n");
                useIt = DPtable[r][c-array[r-1]] + 1;
                loseIt = DPtable[r-1][c];
                if (useIt <= loseIt) { 
                    //if 'use it' requires fewer coins than 'lose it,' then 
                    //'use it' coins are needed. 
                    DPtable[r][c] = useIt;
                } 
                else { 
                    //if 'lose it' requires fewer coins, 'lose it' coins are needed 
                    DPtable[r][c] = loseIt; 
                }
            }
        }
    }

    return DPtable[numRows][numCols];

}

int main() {
    const int array[] = {1,5,10,25};
    const int* stamps = &array[0];
    printf("%d", min_number_of_stamps(stamps, 4, 44));
}

当我的内部 for 循环到达 r=4 和 c=0 的情况时，我遇到了段错误。我把调试打印语句留在里面是因为我很懒，但是你可以看到我在哪里卡住了。如果我在 for 循环之外访问数组中的相同位置，则没有问题。但是在 for 循环中，在它为数组元素输出“4,0”和为 if 情况输出“1”之后，我收到一条“Segmentation fault: 11”消息。有人能看到我遗漏了什么吗？

Answer 1

学习为您的编译器启用警告和调试，即 Linux 上的 gcc -g -Wall。

学习使用调试器，即 Linux 上的 gdb -tui。

考虑使用 valgrind

编辑在 Web 上很容易找到 GCC、GDB 和 ValGrind 的许多教程(多种语言，例如英语、法语......)。