C语言 棒材切割问题自上而下递归实现中的价格不匹配

Question

我正在学习如何解决棒材切割最大利润的问题。但是当我编写这段代码时，它并没有产生一个激烈的结果。他给出的结果是 20，但正确的结果是 10。

这是代码：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int _max(int a, int b) { if (a > b) return a; else return b; }
int cut_rod(int prices[], int size)
{
if (size == 0) return size;
int max = 0;
for (int i = 1; i <= size; i++)
{
max = _max(max, prices[i] + cut_rod(prices, size - i));
}
return max;
}
int main(int argc, char** argv)
{
int arr[] = { 1,5,8,9};
int size = sizeof(arr) / sizeof(arr[0]);
int max = cut_rod(arr, size);
printf("Maximum Obtainable Value is %d", max);
getchar();
return 0;
}

此代码中可能出现什么问题？

Answer 1

for (int i = 0; i < size; i++)
{
max = _max(max, prices[i] + cut_rod(prices, size - i - 1));
}

这是你的错误：cut_rod(prices, size - i - 1))和for (int i = 0; i < size; i++)

这是一个算法规则。 请仔细阅读算法的说明。

您从 arr[1] = 价格 [1] = 5(您的值(开始，但在描述算法中

我们应该从 arr[0] = 价格 [0] = 1(您的值(开始

为了更好地理解，你可以拿纸来解析这段代码(递归(

for (int i = 0; i < size; i++)
{
max = _max(max, prices[i] + cut_rod(prices, size - i - 1));
}

Answer 2

你越界访问 arr[]/prices[] 数组

for (int i = 1; i <= size; i++)
{
max = _max(max, prices[i] + cut_rod(prices, size - i));
}

由于数组索引在 C 中从 0 开始计数，大小为 4，但没有arr[4]。