1.20 动态规划（简单）-Toy模板网

这篇具有很好参考价值的文章主要介绍了1.20 动态规划（简单）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划解题思路

动态规划的做题步骤

1. 爬楼梯

2.杨辉三角

3.买卖股票的最佳时机

动态规划解题思路

1.20 动态规划（简单）,动态规划,算法

动态规划的做题步骤

1.20 动态规划（简单）,动态规划,算法

1. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

1 <= n <= 45

分析：从分析来看，类似于斐波那契数列，f(0)=0,f(1)=1,f(2)=2,要用递归

1.20 动态规划（简单）,动态规划,算法

#include <bits/stdc++.h>

using namespace std;


int fb(int n)
{
    if(n==1) return 1;
    if(n==2) return 2;
    return fb(n-1)+fb(n-2);
}
main()
{
    int n;
    cin>>n;
    cout<<fb(n);

}

2.杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

1.20 动态规划（简单）,动态规划,算法

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

1 <= numRows <= 30

分析： 1.20 动态规划（简单）,动态规划,算法

#include <bits/stdc++.h>

using namespace std;

int dp[10][10];
void output(int n)
{
    int i,j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=i; j++)
        {
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }
}
void init(int n)
{
    int i;
    for(i=1; i<=n; i++)
    {
        dp[i][i]=1;
        dp[i][1]=1;
    }
}
void f(int n)
{
    for(int i=3; i<=n; i++)
    {
        for(int j=2; j<i; j++)
        {
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
        }
    }
}
main()
{
    int n;
    cin>>n;
    init(n);
    f(n);
    output(n);


}

3.买卖股票的最佳时机

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 104

分析：dp[i]表示前i天的最大利润 1.20 动态规划（简单）,动态规划,算法文章来源地址https://www.toymoban.com/news/detail-820525.html

#include <bits/stdc++.h>

using namespace std;

main()
{
    int x,i,n=1;
    int price[10];
    int minprice=100,maxprofit=0;
    while(cin>>x)
    {
        price[n]=x;
        n++;
    }
//      for(i=1;i<n;i++) cout<<price[i]<<" ";
    for(i=1;i<n;i++)
    {
        minprice=min(price[i],minprice);
        maxprofit=max(maxprofit,price[i]-minprice);
    }
cout<<maxprofit;


}

到了这里，关于1.20 动态规划（简单）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！