DP动态规划入门学习--1

朱雀 2023-07-13 03:20 36阅读 0赞

## DP经典问题（选或不选） ##

题目搬自：[https://www.bilibili.com/video/av18512769/][https_www.bilibili.com_video_av18512769]

**以题目为例，在一个数组arr中，找出一组不相邻的数字，使得最后的和最大.**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1][]

C语言代码：

#include <stdio.h>
    //返回两个数中的最大值
    int max(int a,int b)
    {
        return a>b?a:b;
    }
    //递归写法 会有重复子问题计算，影响效率
    int rec_opt(int arr[],int i)
    {
        int m,n;
        if(i==0)
            return arr[0];
        else if (i==1)
            return max(arr[0],arr[1]);
        else
        {
            m = rec_opt(arr,i-2)+arr[i];
            n = rec_opt(arr,i-1);
            return max(m,n);
        }
    }
    //非递归写法
    int opt(int arr[],int i)
    {
        int j,m,n;
        int b[i];
        b[0] = arr[0];
        b[1] = max(arr[0],arr[1]);
        for(j=2;j<=i;j++)
        {
            m = b[j-2]+arr[j];
            n = b[j-1];
            //存储子问题 加快速度
            b[j] = max(m,n);
        }
        //返回最终结果
        return b[i];
    }
    int main()
    {
       int arr[] ={1,2,4,1,7,8,3} ,max_num;
       //max_num = rec_opt(arr,6);
       max_num = opt(arr,6);
       printf("%d\n",max_num);
    }

python代码：

#递归代码
    arr = [1,2,4,1,7,8,3]
    def rec_opt(arr,i):
        if i == 0:
            return arr[0]
        elif i == 1:
            return max(arr[0],arr[1])
        else:
            m = rec_opt(arr,i-2)+arr[i]
            n = rec_opt(arr,i-1)
            return max(m,n)
    rec_opt(arr,6)

import numpy as np
    arr = [1,2,4,1,7,8,3]
    #非递归代码
    def opt(arr):
        #生成len(arr)的值全为0的数组
        opt = np.zeros(len(arr))
        opt[0] = arr[0]
        opt[1] = max(arr[0],arr[1])
        for i in range(2,len(arr)):
            m = opt[i-2]+arr[i]
            n = opt[i-1]
            opt[i] = max(m,n)
        return opt[len(arr)-1]
    opt(arr)

[https_www.bilibili.com_video_av18512769]: https://www.bilibili.com/video/av18512769/?spm_id_from=333.788.videocard.0
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200309214403650.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200309214432432.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0,size_16,color_FFFFFF,t_70