动态规划入门：从零开始了解DP的核心思想

创作时间:

作者:

@小白创作中心

动态规划入门：从零开始了解DP的核心思想

引用

CSDN

https://blog.csdn.net/a3475754705/article/details/146275346

动态规划（Dynamic Programming，简称DP）是一种在计算机科学和数学中常用的算法设计方法，主要用于解决最优化问题。它通过将问题分解为子问题，并存储子问题的解来避免重复计算，从而提高算法效率。本文将从零开始介绍动态规划的核心思想，通过具体实例帮助读者理解这一重要算法。

一、动态规划概述

动态规划（Dynamic Programming, DP）是一种解决复杂问题的算法设计方法，通过将问题分解为子问题，并存储子问题的解（通常使用表格或数组），避免重复计算，从而提高效率。

二、动态规划的步骤

定义状态：确定问题的状态表示，通常用dp[i]或dp[i][j]表示。
确定状态转移方程：找出状态之间的关系，通常为递推公式。如在斐波那契数列中，dp[i] = dp[i-1] + dp[i-2]。
初始化：初始化边界条件，即最小子问题的解。如在斐波那契数列中，dp[0] = 0和dp[1] = 1。
确定计算顺序：确定如何填充状态表，确保在当前计算状态时，依赖的子问题已经解决。
计算并储存结果：根据前面的步骤逐步计算并储存结果。
返回最终结果：返回原问题的解。

三、常见的动态规划

以下将通过两个例题来介绍动态规划的做法：

1. 最大子段和

题目链接：最大子段和

根据上面的步骤我们来分析一下步骤：

首先定义状态，用b[i]表示以第i个元素结尾的最大子数组和。
对于每个元素a[i]，有两种选择：

将a[i]加入到以a[i-1]结尾的子数组中，形成一个新的子数组，其和为b[i-1] + a[i]；
以a[i]作为新的子数组的起点，其和为a[i]。

选择两者中较大的值作为b[i]，即b[i]=max(a[i],b[i−1]+a[i])。
初始化，当i = 0时，只有一个元素a[0]，因此b[0] = a[0]。
从i = 1开始，逐步计算b[i]。
最终结果是所有b[i]中的最大值，即sum = max(b[0], b[1], ..., b[n-1])。

下面是实现代码：

#include<bits/stdc++.h>
using namespace std;
long long a[200005],b[200005],sum=-10000000000;
int main()
{
    long long n,i,j;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        if(i==0)
        {
            b[0]=a[0];
        }
        else
        {
            b[i]=max(a[i],b[i-1]+a[i]);
        }
        sum=max(sum,b[i]);
    }
    cout<<sum;
    return 0;
}

2. 不容易系列之(3)—— LELE的RPG难题

题目链接：不容易系列之(3)—— LELE的RPG难题

设a[i]表示前i个方格满足条件的涂法总数。第i个方格的颜色与第1个方格的颜色相同，那么第i个方格只有1种选择（必须与第i−1个方格颜色不同）；如果第i个方格的颜色与第1个方格的颜色不同，那么第i个方格有2种选择（因为不能与第i−1个方格颜色相同）。由此推出递推关系a[i]=a[i-1]+2*a[i-2]。

下面是实现代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    long long a[55];
    a[1]=3;
    a[2]=6;
    a[3]=6;
    for(int i=4;i<=50;i++)
    {
        a[i]=a[i-1]+2*a[i-2];
    }
    while(scanf("%d",&n)!=EOF)
    {
        printf("%lld",a[n]);
    }
    return 0;
}