JackQin

用户名：2219529518

访问量：13783

签　名：

真正的大师永远怀着一颗学徒的心。

等　　级
排　　名	663
经　　验	4016
参赛次数	5
文章发表	25
年　　龄	18
在职情况	学生
学　　校	上海交通大学
专　　业	计算机科学

　　自我简介：

纵然疾风起，人生不言弃。

TA的其他文章

二分时间+区间覆盖
浏览：1218

线性dp（打家劫舍系列）
浏览：1883

你可能喜欢

动态规划基础典例

　　作者: JackQin　　　　发表时间：2019-11-17 12:47:41 浏览：336　|　评论：0　

原题链接：超级楼梯

```c
#include<stdio.h>
int slove(int n);
int main()
{
	int n,x;
	scanf("%d", &n);
	while (n--)//持续读取
	{
		scanf("%d", &x);
	printf("%d\n", slove(x));
	}

return 0;
}
int slove(int n)
{
	if (n <= 1)\\0，1和2都是边界条件，需要返回
		return 0;
	if (n == 2)
		return 1;
	if (n == 3)
		return 2;
		return slove(n - 1) + slove(n - 2);//分解为上两级方法并求和
}
这是第二次讲这道题了，非常典型的一道动态规划的题目
1，首先明确第n级楼梯只有两种上去方法（一种是从n-1级直接上去，另一种是从n-2级跨上去）从第n-2级走两个1级的那一种被包含在n-1的那种中了（基本思想）
2，那么是不是可以这样认为：每一次到第n级都可以分解为上两级（n-1和n-2）的方法之和
3，所以基本思路就是递归（不懂递归的同学可以自行百度一下，算法里面很重要一部分），其中也有分治的思想
4，那么是不是递归（分治）到最后会有1，2，3级三种情况？（可能会出现0的情况），那么我们就需要对此做出处理，这就是动态规划里面的重中之重：***边界条件**
*
5，最后如果有不懂什么是动态规划的同学，一定要去学习了，不论是算法还是数据结构，亦或是后面的发展，动态规划都是一个很重要的部分，最后谢谢大家的阅读
```# MarkDown编辑器基本使用说明

**如果这是您第一次使用MarkDown编辑器，建议先阅读这篇文章了解一下Markdown的基本使用方法。**

## 实时预览、全屏显示

![](/image_editor_upload/20190606013233_25630.png)

**编辑器左边是输入框，右边是实际效果预览，可以点击编辑器上方界面小眼睛按钮来打开或关闭实时预览，如果感觉基本编辑界面太小太窄也可以使用全屏。**

## 插入代码

**请不要在编辑框中直接粘贴代码，请使用代码块。**
- #### 代码块
![](/image_editor_upload/20190606022155_81717.png)
![](/image_editor_upload/20190606024121_61585.png)

**点击图标“代码块（多语言风格）”，即可在其中输入想要插入的代码。**

*输入与预览图例：*
	![](/image_editor_upload/20190606022918_54401.png)

**如上图代码块的开头与结尾都有三个间隔号（键盘左上角Esc下方按键），开头三个间隔号后的“c”即为代码语言。下面是一个例子：**

```c
	#include<stdio.h>
	int main()
	{
		int a,b;
		while(~scanf("%d%d", &a, &b))printf("%d\n",a+b);
		return 0;
	}
	```

- #### 行内代码
![](/image_editor_upload/20190606040412_74577.png)

**请点击“行内代码”按钮，再输入代码。**

*输入与预览图例：*
	![](/image_editor_upload/20190606040626_28452.png)

**如上图，与代码块不同，行内代码开头和结尾只有一个间隔号。下面是一个例子：**

`#include<stdio.h>`的作用是引入头文件！

## 标题样式

**标题支持6种样式，可点击H1~H6按钮变更标题样式；**

![](/image_editor_upload/20190606013846_99194.png)

**也可以直接输入“#”来编辑，“#”对应H1,“##”对应H2……**

*输入与预览图例：*
![](/image_editor_upload/20190606014119_69661.png)

## 文字样式

![](/image_editor_upload/20190606014703_35680.png)

**可点击按钮变更样式，或直接输入标记语法。**

*输入与预览图例：*
![](/image_editor_upload/20190606021227_16757.png)

**如上图中直接输入标记语法符号也可以达到想要的效果。下面是几个例子：**

*强调文本* _强调文本_
**加粗文本** __加粗文本__
　　==标记文本==
~~删除文本~~
> 引用文本

## 插入图片

![](/image_editor_upload/20190606023726_46319.png)

**点击“添加图片”按钮即可插入想要的图片，但上传有大小限制，图片如果过大请修改本地图片属性后再上传。**

## 插入表格

![](/image_editor_upload/20190606024844_48835.png)

**点击“添加表格”，填写一些基本属性，点击确定得到下图结果：**

![](/image_editor_upload/20190606025647_67742.png)

**在左边输入框中填入一些信息，即可完成表格：**

*输入与预览图例：*
![](/image_editor_upload/20190606025824_42776.png)

**你可以在左边输入框中任意增减图例中的竖线符号来调整表格格式。下面是一个例子：**

| 内容板块 | 大纲内容 | 学习目标 | …… |
| ------------ | ------------ |
| 标准语法 | 标准C语言全语法 | 熟练掌握C语言标准语法 |
| 实验与探究 | C语言特性  | 理解C语言底层原理 | 其他内容 |

## 列表

![](/image_editor_upload/20190606032543_63651.png)

**编辑一个列表，点击图标“无须列表”或“有序列表”，即可编辑内容，编辑好后按回车键，再次点击列表按钮开始编辑下一条。**

*输入与预览图例：*
![](/image_editor_upload/20190606033831_52890.png)

**你可以如上图中根据需求灵活使用其他标记语法与Tab键，改变文字样式与格式。下面是一个例子：**

- #### C语言快速入门

1. C语言第一个简单实例
	1. 实例说明

- **C语言的数据类型**

- 变量与常量数据
	- 数据类型和关键字
	- 本章总结与作业

## 科学公式 TeX(KaTeX)

**请在编辑器的预编辑内容中查看公式语法示例**

$$E=mc^2$$

行内的公式$$E=mc^2$$行内的公式。

$$x > y$$

$$$\sqrt{3x-1}+(1+x)^2$$$

$$\sin(\alpha)^{\theta}=\sum_{i=0}^{n}(x^i + \cos(f))$$

多行公式：

```math
\displaystyle
\left( \sum\_{k=1}^n a\_k b\_k \right)^2
\leq
\left( \sum\_{k=1}^n a\_k^2 \right)
\left( \sum\_{k=1}^n b\_k^2 \right)
```

```katex
\displaystyle
    \frac{1}{
        \Bigl(\sqrt{\phi \sqrt{5}}-\phi\Bigr) e^{
        \frac25 \pi}} = 1+\frac{e^{-2\pi}} {1+\frac{e^{-4\pi}} {
        1+\frac{e^{-6\pi}}
        {1+\frac{e^{-8\pi}}
         {1+\cdots} }
        }
    }
```

```latex
f(x) = \int_{-\infty}^\infty
    \hat f(\xi)\,e^{2 \pi i \xi x}
    \,d\xi
```

## 关于空格

**想要给一段文字添加多个　*空格符*　？**

**　　如果一定要输入多个连续空格符，可以切换输入法至全角输入（默认半角），然后再输入空格；**

------------

### 来试试编辑一篇文章吧，祝您使用愉快！

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JackQin

TA的其他文章

你可能喜欢

【明明的随机数】（C语言代码）

Tom数（C语言代码）

C语言训练-字符串正反连接（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

动态规划基础典例

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

A+B for Input-Output Practice (V) （C语言代码）

1126题解

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

JackQin

TA的其他文章

你可能喜欢

【明明的随机数】 （C语言代码）

Tom数 （C语言代码）

C语言训练-字符串正反连接 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

动态规划基础典例

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

A+B for Input-Output Practice (V) （C语言代码）

1126题解

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

【明明的随机数】（C语言代码）

Tom数（C语言代码）

C语言训练-字符串正反连接（C语言代码）

　　评论区

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）