• 数据结构 贪心算法 动态规划 学习笔记


    首先我们了解一下贪心算法  

    举例 :一根绳子  长度为8  怎么剪  每段绳子的乘积最大?

    这里我们找规律  只有剪成n个长度为三的绳子 乘积最大  但是 这样剪会遇到以下几种情况

    1.剩了一段长度为1的绳子

    如果遇到这种情况 我们就少剪出一段长度为3的绳子  用这一段和剩下的长度为1的绳子拼一下 得到长度为4 的绳子  再将它剪成2段长度为2 的绳子

    2.剩了一段长度为2的绳子

    假设减了n个长度为3的绳子  剩了一段长度为2的绳子 

    乘积=3*n*2;

    3.没剩

    乘积=3*n;

    具体代码如下

    1. int cNum(int Num)
    2. {
    3. //排除小于等于3的情况
    4. if (Num < 2)
    5. return 0;
    6. if (Num == 2)
    7. return 2;
    8. if (Num == 3)
    9. return 3;
    10. //绳子大于3 nCountof3记录段数
    11. int nCountof3 = Num / 3;
    12. if (Num - nCountof3 == 1)//余下的绳子长度=1 少剪一段长度为3的 用于和长度为1的拼
    13. nCountof3--;
    14. //判断剩了的绳子可以剪成几段长度为2的绳子
    15. int nCountof2 =(Num - nCountof3 *3)/ 2;
    16. return (int)pow(3, nCountof3) *(int)pow(2, nCountof2);//乘积=3的(nCountof3)次方*2的(nCountof2)次方
    17. }

    接下来  了解一下动态规划 

    动态分配一般当前的问题会与之前处理的两个问题有关联

      如:

    斐波那契数列 f(n)=f(n-1)+f(n-2);

    一般我们采用动态分配的方法时  都会生成这样一种解决方案的函数  

    在这道题中 我们的思路是

    开辟一个数组  

    当前元素等于   下标相加等于当前元素的下标  的两个元素的乘积的最大值   

    如当前元素为4     1,3     2,2  符合    那么看   pArr[1]*pArr[3]   和  pArr[2]*pArr[2] 谁大  大的乘积为pArr[4]的值

    代码如下

    1. int DP(int Num)
    2. {
    3. if (Num < 2)
    4. return 0;
    5. if (Num == 2)
    6. return 2;
    7. if (Num == 3)
    8. return 3;
    9. int* pArr = new int[Num + 1];
    10. ::memset(pArr, 0, sizeof(int) * (Num + 1));
    11. pArr[0] = 0;
    12. pArr[1] = 1;
    13. pArr[2] = 2;
    14. pArr[3] = 3;
    15. int Sum = 0;
    16. for (int i = 4; i <= Num; i++)
    17. {
    18. int max = 0;
    19. for (int j = 0; j < i / 2; j++)
    20. {
    21. if (pArr[j+1] * pArr[i - j - 1] > max)
    22. {
    23. max=pArr[j+1] * pArr[i - j - 1];
    24. }
    25. }
    26. pArr[i] = max;
    27. Sum = max;
    28. }
    29. delete []pArr;
    30. pArr = NULL;
    31. return Sum;
    32. }

  • 相关阅读:
    正态分布的推导笔记
    Celery框架从入门到精通
    【NLP笔记】文本向量化
    苹果笔的代替笔有哪些?Ipad好用电容笔测评
    .NET Core WebApi第7讲:项目的发布与部署
    Android AndroidStudro版本gradle版本对应
    在Vue中使用腾讯云COS(建议正式环境使用)
    Baize_h1mini六足机器人零件准备
    DataGridView控件
    深度解读《深度探索C++对象模型》之数据成员的存取效率分析(二)
  • 原文地址:https://blog.csdn.net/van9527/article/details/126318167