动态规划

标签：结果 int com 自顶向下 https 动态 规划 dp

在其他博客看到的一句话：计算机归根结底只会做一件事情——穷举；所有的算法都是如何让计算机“聪明”的穷举。

什么是动态规划

动态规划是将复杂问题分解成小问题求解的策略，与分治算法不同的是，分治算法要求各个子问题是相互独立的，而动态规划各个子问题是相互关联的。

自顶向下

递归是常见的自顶向下的问题。使用斐波那契数进行举例：要求f(10)的结果，需要知道f(9)的结果，之后类推直到需要知道f(1)和f(2)的值，最后逐步返回最终得到结果。这种从结果找到初始值的思路就叫做自顶向下。

 ```

int Fib(int n) {     //初始值f(0)=1,f(1)=1     if(n==1||n==2)     return 1;
    return Fib(n-1)+Fib(n-2);
}

```

自底向上

动态规划是一种自底向上的问题。同样是斐波那契数问题：还是要求f(10)的结果，这次从f(1)和f(2)开始向上求值，直到得到f(10)结果，最后返回结果。这种从初始条件推到结果得思路就为自顶向下。

```

int Fibi(int n) {     std::vector<int> dp(n,0);     int i=0;     dp[0]=1;     dp[1]=1;     for(i=2;i<n;i++)     {         dp[i]=dp[i-1]+dp[i-2];     }     return dp[n-1]; }

```

自己认为这两种方式往往同时考虑，得出结果，最后根据实际情况选择具体得实现方式。

状态转移方程

状态转移方程其实就是解决问题的核心，上面的dp[i]=dp[i-1]+dp[i-2]就是状态转移方程。

动态规划示例问题

爬楼梯题目 ：

https://leetcode.com/problems/climbing-stairs/

有N级楼梯，一次可以爬1级或2级，问有几种爬法到顶。

解题思路：设定楼梯级数推理，得到结果类似斐波那契数列。

```

int climbStairs(int n) {     std::vector<int> dp(n,0);     int i=0;     dp[0]=1;     dp[1]=2;     for(i=2;i<n;i++)     {         dp[i]=dp[i-1]+dp[i-2];     }     return dp[n-1]; }

```

问题优化（滚动数组）

根据对上述算法的分析，发现并不需要列举每个数组，只需要对三个状态数据保存即可。使用滚动数组的思想进行优化：

```

int Fibi(int n) {     int dp;     int i=0,     pre1=1,     pre2=2;     for(i=2;i<n;i++)     {         dp=pre2+pre1;         pre1=pre2;         pre2=dp;     }     return dp; }

```

滚动数组简单的理解就是让数组滚动起来，每次使用固定的几个空间存储，来达到压缩、节省存储空间的作用。

 

写到最后

最后插一句，斐波那契数列其实可以直接使用公式得出结果。

还有这次的博客参考文章较少，很多有主观思想的存在，希望大佬即时指出问题，非常感谢。

 

---

 

参考文章：

https://houbb.github.io/2020/01/23/data-struct-learn-07-base-dp#dynamic-programming

https://mp.weixin.qq.com/s?__biz=MzI2OTE0ODY5Mw==&mid=2247525996&idx=1&sn=3d76f5fc2feb0559b4c92949799975fa&chksm=ebd22c9d8f67e1092763fb3e582a7141482e85220e61e5a359775545e902954f3228873b3b53&scene=27

https://blog.csdn.net/qq_41655898/article/details/120174686

https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145

https://www.cnblogs.com/overxus/p/18167834

 

标签：结果,int,com,自顶向下,https,动态,规划,dp
From： https://www.cnblogs.com/LJianYu/p/18678484