【Hello Algorithm】 暴力递归到动态规划 -- 总结

动态规划总结

什么样的问题可以动态规划

我们发现过程中有重复调用的问题 我们可以使用动态规划

暴力递归和动态规划的关系

如果一个暴力递归问题 有重复调用的过程 我们就可以把它优化成动态规划

所有的动态规划问题一定可以转化成暴力递归

但是并不是所有的暴力递归都可以转化城动态规划

如何找到某个问题的动态规划方式

1. 设计暴力递归
2. 分析有没有重复解
3. 实现记忆化搜索
4. 改写动态规划

暴力递归的设计原则

一般来说 我们有几个可变参数 我们就有一张几维表

1. 我们要设计的可变参数类型一定不要超过整形 如果我们设计的一个可变参数是数组 要改成动态规划是十分困难的
2. 如果我们违反了原则1 可变参数类型突破到了一维线性结构 那么我们接下来就只能使用一个可变参数 并且要使用记忆化搜索的方式来进行动态规划
3. 可变参数的个数 能省则省

暴力递归尝试的四种模型

• 从左往右尝试模型
• 范围方式模型
• 样本对应模型
• 业务限制模型

N皇后问题

本题是leetcode原题

题目连接： N皇后问题

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案个数.

我们解决n皇后问题的思路如下

---

我们选择每一行都放一个棋子 这样子我们就能保证最基本的行不冲突 之后我们后面的棋子只需要保证不同列不同斜线就可以

那么现在的问题就变成了我们如何保证不同列不同斜线呢？

我们这里可以选择使用一个数组来记录每一行的列数 之后使用公式判断即可（同斜线公式 行相减的绝对值 = 列相减的绝对值 ）

代码表示如下

bool IS_VAILD(vector<int>& cord , int i , int j)
{
  for (int k = 0 ; k < i ; k++)    
  {    
    if (j == cord[k] || abs(cord[k] - j) == abs(i - k))
    {    
      return false;    
    }                                                                                                                                                    
  }    
  return true;    
}    
    
// 0 ~ n-1    
int process(int i , vector<int>& cord , int n)    
{    
  if (i == n)    
  {    
    return 1;    
  }    
    
  int ans = 0;    
  for (int j = 0; j < n; j++)    
  {    
    if (IS_VAILD(cord , i , j))    
    {    
      cord[i] = j;    
      ans += process(i+1 , cord , n);    
    }    
  }    
    
  return ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

这就是一个我们可以写递归但是写不了动态规划的题目