当前位置: 首页> 房产> 家装 > 动态规划算法

动态规划算法

时间:2025/7/11 23:42:28来源:https://blog.csdn.net/qq_62821433/article/details/139559375 浏览次数:0次

动态规划解法:

1.确定dp数组以及下标含义

2.确定递推公式

3.dp数组如何初始化

4.如何遍历数组

5.举例推导

例如下面一到简单题

斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1

给定 n ,请计算 F(n) 。 

递归解法 

int fib(int N) {if(N<=1)return N;return fib(N-1)+fib(N-2);
}

这道斐波那契数列,很多同学直接一手递归就解决,但是递归的时间复杂度O(2^n)明显要高,但是我们今天重点是动态规划 

int fib(int N) {if (N <= 1) return N;vector<int> dp(N + 1);dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[N];}

可以看到动态规划的时间复杂度是O(N),比递归好了不少,虽然空间复杂度是O(N),但是实际只需要两个变量存放前面的两个值,所以空间复杂度还可以优化到O(1)

int fib(int N) {if (N <= 1) return N;int dp[2];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {int sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];

关键字:动态规划算法

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: