算法导论 动态规划 钢条切割

--------------------------------------------------------------------------------

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<limits.h>
#define MAX 1000
#define max 11
int p_value[max] = { 0,1,5,8,9,10,17,17,20,24,30 };
int max_profit(int* p, int n);


int main()
{
 int n;
 scanf("%d", &n);
 max_profit(p_value, n);
 printf("%d", max_profit(p_value, n) );

}

int max_profit(int* p, int n) {
 if (0 == n)
  return 0;

 int tmp_max = INT_MIN;
 int tmp;
 for (int i = 1; i <= n; i++) {
  tmp = p_value[i] + max_profit(p, n - i);
  tmp > tmp_max ? tmp_max = tmp : tmp_max;
  if (i > max-1)
   break;
 }
 return tmp_max;

}
-------------------------------------------------------------------------------

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<limits.h>
#define MAX 1000
#define max 11
int p_value[max] = { 0,1,5,8,9,10,17,17,20,24,30 };
int max_profit(int* p, int n);
int memorandum[MAX] = {0};

int main()
{
 int n;
 scanf("%d", &n);
 max_profit(p_value, n);
 printf("%d", memorandum[n]);

}

int max_profit(int* p, int n) {
 if (0 == n)
  return 0;
 if (memorandum[n] > 0)
  if (memorandum[n] > 0)
   return memorandum[n];
 int tmp_max = INT_MIN;
 int tmp;
 for (int i = 1; i <= n; i++) {
  tmp = p_value[i] + max_profit(p, n - i);
  tmp > tmp_max ? tmp_max = tmp : tmp_max;
  if (i > max-1)
   break;
 }
 memorandum[n] = tmp_max;

}
-------------------------------------------------------------------------------------------------

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<limits.h>
#define MAX 1000
#define max 11
int p_value[max] = { 0,1,5,8,9,10,17,17,20,24,30 };
int max_profit(int *p_value, int n);
int array[1000] = { 0 };
int array_n[1000] = { 0 };


int main()
{
    int n;
    scanf("%d", &n);
    max_profit(p_value, n);

;

}

int max_profit(int*p_value, int n) {
    
    int q = INT_MIN;
    int tmp,tmptmp;
    for (int j = 1; j <= n; j++) {
        for (int i = 1; i <= j; i++) {
            tmp = p_value[i] + array[j - i];
            if (tmp > q) {
                q = tmp;
                tmptmp = i;
            }
            if (i > max)
                break;
        }
        array[j] = q;
        array_n[j] = tmptmp;
    }
    return array[n];
}