动态规划

待我称王封你为后i 2023-08-17 17:49 32阅读 0赞

问题

  1.      给出一个数组，求不相邻的数之和最大

递推式

1448741-20190823095502243-1064465352.png

代码

  1. //求不相邻的最大数之和
  2. #include <iostream>
  3. using namespace std;
  4. #define max(a,b) (a > b ? a : b)
  6. int arr[] = {
  7.     1, 2, 4, 1, 7, 8, 3};
  9. //递归求解
  10. int rec_opt(int i) {
  11.     if(i == 0) {
  12.         return arr[0];
  13.     }
  14.     else if(i == 1) {
  15.         return max(arr[0], arr[1]);
  16.     }
  17.     else {
  18.         int A = arr[i] + rec_opt(i -2);
  19.         int B = rec_opt(i - 1);
  20.         return max(A, B);
  21.     }
  22. }
  24. //非递归求解
  25. int dp_opt() {
  26.     int len_arr = sizeof(arr) / sizeof(int);
  27.     //此数组用存放最大值的
  28.     int *opt = new int[len_arr];
  29.     opt[0] = arr[0];
  30.     opt[1] = max(arr[0], arr[1]);
  31.     for(int i = 2; i < len_arr; i++) {
  32.         int A = opt[i - 2] + arr[i];
  33.         int B = opt[i - 1];
  34.         opt[i] = max(A, B);
  35.     }
  36.     return opt[len_arr - 1];
  37. }
  39. int main() {
  40.     cout << rec_opt(6) << endl;
  41.     cout << dp_opt() << endl;
  42.     return 0;
  43. }

转载于:https://www.cnblogs.com/Gzu\_zb/p/11398276.html

发表评论

表情：
评论列表 （有 0 条评论，32人围观）

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

相关阅读

    相关 动态规划

    一：概念： 和分冶法相似，不同之处在于前者是把问题划分为互不相交的子问题，而动态规划会出现子问题重叠的情况。通常用来求解最优化问题。。 基本步骤： ①：刻画一个最优

    我就是我我就是我/ 0 赞/ 91 阅读

    相关 动态规划

    -------------------- 动态规划的设计思想 动态规划（DP）\[1\]通过分解成子问题解决了给定复杂的问题，并存储子问题的结果，以避免再次计算相同的结

    柔情只为你懂柔情只为你懂/ 0 赞/ 315 阅读

    相关 动态规划

    1. 首先，动态规划不是一个特定的算法，它代表的是一种思想，一种手段 2. 动态规划方法往往用于求解“最优化问题”，能用动态规划求解的问题的前提是问题具有“最优子结构性质”

    刺骨的言语ヽ痛彻心扉刺骨的言语ヽ痛彻心扉/ 0 赞/ 166 阅读

    相关 动态规划

    首先是概念:动态规划就是将原问题划分为简单的几个小问题（有点类似与分治法?但是分治法中的各个小问题是相互独立的，彼此之间不会产生影响，但是动态规划中所得的值和前面相关，当前的解

    青旅半醒青旅半醒/ 0 赞/ 377 阅读

    相关 动态规划

    > 给定两个字符串A和B，返回两个字符串的最长公共子序列的长度。例如，A=”1A2C3D4B56”，B=”B1D23CA45B6A”，”123456”或者”12C4B6”都是最

    以你之姓@以你之姓@/ 0 赞/ 383 阅读

    相关 动态规划

    基本思想：     动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 区别：     与

    ゞ 浴缸里的玫瑰ゞ 浴缸里的玫瑰/ 0 赞/ 502 阅读

    相关 动态规划

    等我有时间了，一定要把《算法导论》啃完，这本书的印刷质量实在太好了，就是烧脑子，滑稽。 适合应用动态规划求解的最优化问题应该具备两个要素： 最优子结构：一个问题的最优解包含

    短命女短命女/ 0 赞/ 404 阅读

    相关 动态规划

     1.题目：最长递增子序列（Longest Increasing Subsequence） 问题描述： > 给定长度为N的数组A，计算A的最长单调递增的子序列（不一定连续）

    妖狐艹你老母妖狐艹你老母/ 0 赞/ 340 阅读