目录
自言自语
一、动态规划例题
问题分析
代码如下（示例）
二、DFS例题
问题分析
代码如下（示例）
自言自语
浑浑噩噩地过了这么多天，还是要好好学一下了（不能让三百打水漂），在此浅浅地记录一下每天的学习内容，也算有些小成果吧。解题步骤部分借鉴大佬们的代码，如有侵权请联系删除。
一、动态规划例题
试题链接：[NOIP2001 提高组] 数的划分 - 洛谷
问题描述：
将整数n分成k份，且每份不能为空，任意两个方案不相同（不考虑顺序）。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5；
5，1，1；
1，5，1.
问有多少种不同的分法。
输入格式：
n，k（6 输出格式： 1个整数，即不同的分法。 输入样例 7 3 输出样例 4 问题分析 这道题具有递推关系，例题所给的7个数，分为3堆。其中一种分法为1，1，5 我们可以将其看成：第一步：给第一堆1个，其他堆不给，且第一堆以后不再考虑； 第二步：给第二堆1个，其他不给，且第二堆不再考虑； 第三步：给第三堆5个。 还可以考虑分法2，2，3. 我们可以将其看成：第一步：给每一堆1个； 第二步：给第一堆1个，其他不给，且第一堆不再考虑； 第三步：给第二堆1个，其他不给，且第二堆不再考虑； 第四步：给第三堆1个。 我们将n个数分为k堆记为（n,k）,则（n,k）可以分为（n-1,k-1）和（n-k,k）两种情况。 则我们可将其写作（n,k）=（n-1,k-1）+（n-k,k）。 我们容易得出，（m,1）成立且只有一种可能，（m,m）成立且只有一种可能，而（i，j）当 i>j 时可再分，当 i 现在我们只需输出（n，k）即可。 代码如下（示例） n,k=map(int,input().split()) ls=[[0 for j in range(201)] for i in range(201)] for i in range(1,200): ls[i][1]=1 ls[i][i]=1 for i in range(3,201): for j in range(2,7): if i>j: ls[i][j]=ls[i-1][j-1]+ls[i-j][j] print(ls[n][k]) 二、DFS例题 试题链接：[USACO1.5] 八皇后 Checker Challenge - 洛谷（蓝桥杯的要vip） 问题描述： 在N×N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。你的任务是，对于给定的N，求出有多少种合法的放置方法。 输入描述： 输入中有一个正整数N≤10，表示棋盘和皇后的数量 输出描述： 为一个正整数，表示对应输入行的皇后的不同放置数量。 输入样例 5 输出样例 10 问题分析 对于一个N×N棋盘，我们可以从第一行开始放皇后，一行一行放，因为它们不能在同一行。 对于DFS问题，我们设置check函数和pd函数，其中check函数判定有没有跑出N行，若他平稳的到了第N+1行，说明找到了一种放置方法，于是我们进行return，回到第N行，并判断在下一个位置放是否可行（当然不可行）；pd函数判断第a个皇后放在该位置是否合理（题目所给的不能在同一列，同一条斜线，即斜率不为1）。 对于DFS函数，我们同样也是递推算法，行数a从第一行找起，首先进行pd(a)，对每一行都可以进行列从1到N遍历，并将其赋值到x[a]，表示皇后在第a行第x[a]列，之后对该位置进行pd，判断第a个皇后放在该处是否可行，若可行，则找下一行的皇后位置（即DFS(a+1)）;若不可行，则进行回溯，看本行下一列的位置是否可行，若该列都不可能（本层遍历结束后），则返回到上一行的遍历（一个遍历套着一个遍历），不断遍历直到所有层的遍历均结束。 代码如下（示例） x=[0]*15 n=0 sum=0 def pd(k): for i in range(1,k): if abs(k-i)==abs(x[k]-x[i]): return 0 elif x[k]==x[i]: return 0 return 1 def check(a): if a>n: global sum sum+=1 else: return False return True def DFS(a): if check(a): return else: for i in range(1,n+1): x[a]=i if pd(a): DFS(a+1) else: continue if __name__=='__main__': n=int(input()) DFS(1) print(sum) 精彩文章
您阅读本篇文章共花了：
发表评论