leetcode动态规划切钢筋

柔情只为你懂 2022-09-11 01:11 110阅读 0赞

钢筋的价值和长度有关，以下为初始数据

v[0] = 0;
        v[1] = 1;
        v[2] = 5;
        v[3] = 8;
        v[4] = 9;//不是最大值，注意
        v[5] = 10;
        v[6] = 20;
        v[7] = 20;
        v[8] = 20;
        v[9] = 20;
        v[10] = 20;

思路

1.  动态规划，只管最后一刀切的位置
2.  需要将n之前的长度的价值最大值求取出来，进行累计

#include<stdio.h>
    #include <string.h>
    #define MAXLEN 1000
    #define MAX(a,b) ((a) >(b)? a:b)
    void  MaxValueC(int n,int *v,int k){ 
        if(n==0 || n==1||n==2|| n==3) { 
            return  ;
        
        } else { 
            for(int j = 0;j<=n;j++)
            for (int i = 0; i<=j&&i<=10; i++) { 
                v[j] = MAX(v[i]+v[j-i],v[j]);
            }
        } 
    }
    
    int MaxValue(int n) { 
        int v[MAXLEN];
        memset(v, 0,sizeof(v));
        int k = 0;
        v[0] = 0;
        v[1] = 1;
        v[2] = 5;
        v[3] = 8;
        v[4] = 9;
        v[5] = 10;
        v[6] = 20;
        v[7] = 20;
        v[8] = 20;
        v[9] = 20;
        v[10] = 20;
    
        MaxValueC(n,v,k);
        for (int i=0; i<=n; i++) { 
            printf("%d ",v[i]);
        }
        printf("\n");
        return v[n];
    }
    
    
    int main () { 
        int n = 30;
        int re = MaxValue(n);
        printf("re = %d\n",re);
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，110人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划题 leetcode

1. [62. 不同路径][62.] 一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人

我不是女神ヾ/ 2022年12月27日 08:51/ 0 赞/ 213 阅读

相关 LeetCode 动态规划专题

这是整理的LeetCode上的动态规划专题背包问题我们将LeetCode上的背包问题进行一个整理，希望之后再遇到以下问题能够快速解决。组合问题 1. 如

亦凉/ 2022年10月17日 01:54/ 0 赞/ 208 阅读

相关 leetcode动态规划切钢筋

钢筋的价值和长度有关，以下为初始数据 v[0] = 0; v[1] = 1; v[2] = 5; v[3] = 8;

柔情只为你懂/ 2022年09月11日 01:11/ 0 赞/ 111 阅读

相关 leetcode动态规划

1. 爬楼梯假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？动态规划模板题，思考方法，1个台

布满荆棘的人生/ 2022年09月05日 04:07/ 0 赞/ 175 阅读

相关 [Leetcode 动态规划]买卖股票

转自http://liangjiabin.com/blog/2015/04/leetcode-best-time-to-buy-and-sell-stock.html

小灰灰/ 2022年06月08日 08:59/ 0 赞/ 179 阅读

相关【leetcode】编辑距离（动态规划）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

旧城等待，/ 2022年02月27日 04:16/ 0 赞/ 288 阅读

相关 leetcode 动态规划类型题

1，Triangle ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 1 int mininumTotal

怼烎@/ 2021年12月03日 08:10/ 0 赞/ 272 阅读

相关 [leetcode]动态规划之PerfectSquare

动态规划之PerfectSquare 题目思考代码数学方法动态规划题目 [leetcode题目入口][lee

客官°小女子只卖身不卖艺/ 2021年09月29日 02:10/ 0 赞/ 316 阅读

相关 [leetcode]动态规划之CountingBits

动态规划之CountingBits 题目思考代码题目 [leetcode入口][leetcode] 思考这道题让我思考了dp数组

心已赠人/ 2021年09月29日 01:40/ 0 赞/ 298 阅读

相关 [leetcode]动态规划之Triangle

动态规划之Triangle 题目思考答案题目 [leetcode入口][leetcode] 思考刚开始想这道题，想着的是建立一维

缺乏、安全感/ 2021年09月28日 14:46/ 0 赞/ 511 阅读