关键词：
声明
本文不介绍dfs、dp算法的基础思路，有想了解的可以自己找资源学习。
本文适合于刚刚接触dfs和dp算法的人，发现两种算法间的内在联系。
本人算法之路走之甚短，如果理解出现问题欢迎大家的指正，我会分享基于我目前理解到的算法思想。
dfs与dp的关系
很多情况下，dfs和dp两种解题方法的思路都是很相似的，这两种算法在一定程度上是可以互相转化的。
想到dfs也就常常会想到dp，当然在一些特定的适用场合下除外。
dp主要运用了预处理的思想，而dfs则是类似于白手起家，一步步探索。一般来讲，能够预处理要好些，好比战争前做好准备。
dfs和dp都是十分重要的基础算法，在各个竞赛中都有涉及，务必精通。
经典例题-数字三角形 - POJ 1163
题目
The Triangle
Description
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5Sample Output
30
dfs思路
解题思路
自顶向下，将每种路径都走一遍。
通过迭代计算到最后一层，记录最后一层的所有值。
最后一层中的最大值即为所求。
具体代码
#include <iostream>
// use vector vessel to write down the final level
#include <vector>
// use 'sort' method in <algorithm>
#include <algorithm>
// use 'greater<T>' functional template in <functional>
#include <functional>
using namespace std;
// the maximum of the triangle ordinal
const int max_ordinal = 100;
// the depth
int num_of_rows;
// save data
int data[max_ordinal][max_ordinal];
// save the data of the final level
vector<int> ans;
void dfs(int level, int sum, int column)
// avoid multi calculate
int current_sum = sum+data[level][column];
// save data which was in final level
if(level+1 == num_of_rows)
ans.push_back(current_sum);
return;
// binary tree
dfs(level+1, current_sum, column);
dfs(level+1, current_sum, column+1);
int main()
cin >> num_of_rows;
for(int i = 0; i < num_of_rows; i++)
for(int j = 0; j <= i; j++)
scanf("%d", &data[i][j]);
dfs(0, 0, 0);
cout << "output data:" << endl;
sort(ans.begin(), ans.end(), greater<int>());
for(int i = 0; i < ans.size(); i++)
cout << ans[i] << "\\t";
if(!((i+1) % 5)) cout << endl;
cout << endl;
return 0;
dp思路
解题思路
dfs的思路是从上到下，而dp的思路是：从第二层开始，每下去一次往回看一下并取上一层相邻两个大的那个。
具体代码
#include <iostream>
// use 'max' method and 'sort' method
#include <algorithm>
// use 'greater<T>' functional template
#include <functional>
using namespace std;
// same as DFS
const int max_ordinal = 100;
int num_of_rows;
int data[max_ordinal][max_ordinal];
// the array of the dp method
int dp[max_ordinal][max_ordinal];
int main()
cin >> num_of_rows;
for(int i = 0; i < num_of_rows; i++)
for(int j = 0; j<= i; j++)
scanf("%d", &data[i][j]);
// dp now
dp[0][0] = data[0][0];
for(int i = 1; i < num_of_rows; i++)
for(int j = 0; j <= i; j++)
if(j-1 >= 0)
dp[i][j] = data[i][j] + max(dp[i-1][j], dp[i-1][j-1]);
else
dp[i][j] = data[i][j] + dp[i-1][j];
// calling 'sort' method
sort(dp[num_of_rows-1], &dp[num_of_rows-1][num_of_rows], greater<int>());
for(int i = 0; i < num_of_rows; i++)
cout << dp[num_of_rows-1][i] << " ";
cout << endl;
cout << "answer is: ";
cout << dp[num_of_rows-1][0] << endl;
return 0;
《算法竞赛入门经典》之“算法设计与优化策略”
一。构造法UVA120 StacksofFlapjacksTimeLimit: 3000MS 64bitIOFormat: %lld&%lluSubmit Status uDebugDescriptionBackgroundStacksandQueuesareoftenconsideredthebreadandbutt 查看详情
算法之dp(代码片段)
一般DP都是有模板的，先初始化，然后找到不同状态下数值的关系，使得某个状态可用另一个状态由一个固定的方式转移而来，列出状态转移方程，这就是DP；例题P1216[USACO1.5]数字三角形NumberTriangles1f[i][j]+=max(f[i-1][j-1],f[i-1][j]);方... 查看详情
ybt1317组合方案（dfs经典例题）超硬核(代码片段)
...了许多问题，经过我的辛苦努力，最后还是AC了，看来想算法远不如实现算法困难：#include<iostream>#include< 查看详情
《算法竞赛入门经典》例题5.4.1(代码片段)
题目：现代数学的著名证明之一是GeorgCantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：第一项是1/1，第二项是是1/2，第三项是2/1，第四项是3/1，第五项是2/2，……。输入n，... 查看详情
一文通数据结构与算法之——贪心算法+常见题型与解题策略+leetcode经典题(代码片段)
文章目录贪心算法1概念1.1心得1.2题目列表2Leetcode经典题2.1分发物品135.分发糖果(非常经典)455.分发饼干[860.柠檬水找零](https://leetcode-cn.com/problems/lemonade-change/)2.2数组序列相关[1005.K次取反后最大化的数组和](https://leetcode-cn.com/problem... 查看详情
c#程序设计之常用数据结构与算法(代码片段)
C#程序设计之常用数据结构与算法例题1例题2例题3例题4例题5例题1题目描述输入一个字符串，统计其中有多少个单词。单词之间用空格分开。代码usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Task... 查看详情
一文通数据结构与算法之——回溯算法+常见题型与解题策略+leetcode经典题(代码片段)
文章目录回溯算法1基本内容1.1回溯算法的框架1.2回溯核心思想1.3回溯法解决的问题1.4题目列表1.4常见问题分析2经典力扣题2.1全排列问题2.1.1没有重复元素的全排列2.1.2含重复元素的递归全排列2.2子集问题2.2.1不含重复元素的子集2... 查看详情
五大经典算法之动态规划(代码片段)
一、概念起源??动态规划，又名DP算法（取自其DynamicProgramming的缩写），最初是运筹学的一个分支，是用来求解决策过程最优化的数学方法。二、基本思想??把多阶段过程转化为一系列单阶段过程，利用各阶段之间的关系，逐个求... 查看详情
图论算法之dfs与bfs
概述（总）DFS是算法中图论部分中最基本的算法之一。对于算法入门者而言，这是一个必须掌握的基本算法。它的算法思想可以运用在很多地方，利用它可以解决很多实际问题，但是深入掌握其原理是我们灵活运用它的关键所在... 查看详情
树形dp(代码片段)
...质：没有环，dfs不会重复，而且具有明显而又严格的层数关系。判断一道题是否是树形dp：首先判断数据结构是否是一棵树，然后是否符合动态规划的要求。如果都符合，那么是一道树形dp的问题。我们需要通过下面几个步骤来... 查看详情
dfs(代码片段)
...关系，而是错综复杂的网状关系。在图中一个比较重要的算法就是，小编接下来将要介绍的DFS算法。下面通过一个具体的例子来介绍DFS算法——用DFS算法求联通块。问题描述如下：油田（OilDepositsUVa572）输入一个m行n列的字符矩... 查看详情
算法入门系列之排序与检索(代码片段)
UVA340 UVA10420时间有点久远，很早之前写的，然后忘记总结了，这道题其实很容易，一行只取第一个字符串，然后按照字典序输出每个字符串的个数。这里有个技巧就是先用scanf获取第一个字符串，然后再用gets直接吸收剩下的... 查看详情
poj2318图论入门之判断直线与点的位置关系(代码片段)
POJ2318链接（http://poj.org/problem?id=2318）图论入门之判断直线与点的位置关系#include<bits/stdc++.h>usingnamespacestd;structnodeintx1,x2,y1,y2;p[5050];boolis_in(intx,inty,inta)intx1=p[a].x1;intx2=p[a].x2;inty1=p 查看详情
算法总结之递推与递归(代码片段)
递推算法递归算法大致包括两方面的内容：1）递归起点；2）递归关系递推起点递归起点一般由题目或者实际情况确定，不由递归关系推出。如果无法确定递归起点，那么递归算法就无法实现。可见，递归起点是递归算法中的重... 查看详情
一文通数据结构与算法之——二叉树+常见题型与解题策略+leetcode经典题(代码片段)
....1递归形式1.2.2非递归，迭代形式1.3遍历方式2剑指Offer算法题2.1题目列表递归遍历序列化和反序列化二叉搜索树2.2实战[剑指Offer27.二叉树的镜像](https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/)[剑指Offe 查看详情
机试指南第二章-经典入门-查找例题自解(代码片段)
...地对某个数字的查找，也可能涉及搜索等相对难度更大的算法。这里先介绍查找的基础概念和方法。例2.9找xAC代码：#include<cstring>#include<iostream>usingnamespacestd;intnum[205];intmain()intn,m,x;memset(num,0,sizeof(num));wh 查看详情
一文通数据结构与算法之——数组+常见题型与解题策略+leetcode经典题(代码片段)
文章目录2数组2.1常见题型及解题策略2.2字符串操作基础2.3删除数组元素2.3.1题库列表2.4双指针技巧2.4.1题库列表2.5数组类操作2.6剑指offer数组题：剑指Offer04.二维数组中的查找剑指Offer11.旋转数组的最小数字剑指Offer17.打印从1... 查看详情
一文通数据结构与算法之——图+常见题型与解题策略+leetcode经典题(代码片段)
文章目录数据结构——图1基本概念1.1图的存储方式1.2有向加权图1.3实现1.4图的遍历1.4.1深度优先遍历图BFS1.4.2广度优先遍历图BFS1.5拓扑排序1.5.1判断有向图是否存在环1.5.2输出拓扑顺序：深度遍历法1.5.3拓扑排序：广度优先... 查看详情