算法篇------动态规划1

动态规划的概念和理解

对动态规划的经验：
1，抽象（状态数组下标的控制，状态数组下标位置的值的意义）。
2, 代码短小精悍，思维复杂庞大。
3， 必须画图。
4， 感悟。

这一类题的求解核心：
首先，不会照搬照抄状态定义，状态转移方程，，，，等等来写，而是自己的感悟过程。
1，将一个大问题划分成一个个子问题。
2，每一步都要求解子问题，因为下一步必须要用到子问题的结果。

题目1—斐波那契数列

我们知道，求解斐波那契数列的过程就是一个典型的动态规划。
0,1,1,2,3,5,8,13,21,34,

这里以一个青蛙跳台阶的例子来说明情况，
大家都知道青蛙跳台阶是一个斐波那契数列，可是为什么是斐波那契数列呢？

牛课网的青蛙跳台阶问题

代码1：递归
时间复杂度： O（n ^ 2） 画出图的时候类似于一颗二叉树，执行的次数取最坏
空间复杂度：O(n) 这里为什么是O（n）？函数栈帧是不断在复用的，举个例子f(5) = f(4) + f(3)
调用f（4）创建相应的栈帧，调用完成然后销毁。 之后才会去调用f(3)

int fib(int n)
{
    if(n == 1)
      return 1;
    else if(n == 2)
      return 2;
    else
      return fib(n - 1) + fib(n - 2);
}
1
2
3
4
5
6
7
8
9

代码2： 用数组存放起来
空间复杂度 : O(N)
时间复杂度：O（N）

    int arr[41] = {0, 1, 2,};
    for(int i = 3; i < 41; i++)
    {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
1
2
3
4
5

代码3：直接用一个值表示每一次计算的结果
空间复杂度： O（1）
时间复杂度：O（n）

 int f1 = 1, f2 = 2;
    int ret = 0;  //结果
    for(int i = 2; i < n; i++)
    {
        ret = f1 + f2;
        f1 = f2;
        f2 = ret;
    }
1
2
3
4
5
6
7
8

题目2-------三角形（中等）

牛客网：三角形

我先吐槽一下一波题目：真的坑坏本宝宝了
它从上向下走的时候，只能：直接向下 或者 右斜向下
也就是（i, j） ---- > (i + 1, j) 或者(i + 1, j + 1)。
我理解的时候是还可以向斜向左， 也就是 k可以到（i + 1, j -1 )。因为题目说的是走到下一行的相邻位置
搞的我把题目想的的复杂，然后巨难受。

思路1代码：
时间复杂度 ： O（n ^ 2）
空间复杂度： O（n ^ 2）

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) 
    {
        int row = triangle.size();
        //最后一行元素的大小
        int col = triangle.back().size();
        vector<vector<int>> vv(triangle);

        for(int i = 1; i < row; i++)
        {
           for(int j = 0; j <= i; j++)
           {
               if(j == 0)
                   vv[i][j] = vv[i-1][j] + triangle[i][j];
               else if(i == j)
                   vv[i][j] = vv[i-1][j - 1] + triangle[i][j];
               else
                   vv[i][j] = min(vv[i-1][j-1], vv[i-1][j]) + triangle[i][j];
           }      
        }
        
        //遍历最后一排求解
        int min = INT_MAX;
        for(int i = 0; i < col; i++)
        {
            if(min > vv[row-1][i])
               min = vv[row-1][i];
        }

        return min;
    }
};
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

思路2代码：
时间复杂度： O（n ^ 2）
空间复杂度： O（n）

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) 
    {
        vector<int> v(triangle.back());
        int row = triangle.size();

        for(int i = row - 2; i >= 0; i--)
        {
            for(int j = 0; j <= i; j++)
            {
                v[j] = min(v[j], v[j + 1]) + triangle[i][j];
            }
        }
        
        return v[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题目3----拆分词句（较难）

牛客网：拆分词句

题目描述：
给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。
例如:
给定s=“nowcode”；
dict=[“now”, “code”].
返回true，因为"nowcode"可以被分割成"now code".

代码：
时间复杂度： O（n ^ 2）
空间复杂度： O（n）

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) 
    {
        int len = s.size() + 1;

        //can_break[i]的值表示：前i个字符是否可以被分割
        vector<bool> can_break(len + 1, false);

        //初始状态：可以理解为0个字符就是可以分割的（可在词典中找到）
        can_break[0] = true;   

        for(int i = 1; i < len + 1; i++)
        {
            
            for(int j = i - 1; j >= 0; j--)
            {
                //前j个字符可以分割， 然后数组中 j + 1到第 j个字符可以分割
                //数组下标的索引 - 1，  另外的话搞不清下标，可以想极限情况
                if(can_break[j] && dict.find(s.substr(j, i - j)) != dict.end())
                {
                    can_break[i] = true;
                    break;
                }
            }
        }
        
        return can_break[len];
    }
};
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

题目4-----路径总数（简单）

牛客网：路径总数
有一个坑： 只有一行一列的时候（起点和终点在一起的时候居然结果为1）。离大谱。

代码：
时间复杂度：O（m * n）
空间复杂度： O（m * n）

class Solution {
public:
    int uniquePaths(int m, int n) 
    {
        //避免那个坑，全部给成1算了
        vector<vector<int>>  vv(m, vector<int>(n, 1));

        for(int i = 1; i < m; i++)
        {
            for(int j = 1; j < n; j++)
            {
                vv[i][j] = vv[i-1][j] + vv[i][j-1];
            }
        }

        return vv[m-1][n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题目5------最小路径和（中等）

牛客网：带权值的最小路径和

代码：
时间复杂度： O（m * n）
空间复杂度： O（m * n）

class Solution {
public:
    int minPathSum(vector<vector<int> >& grid) 
    {
        int row = grid.size();
        int col = grid[0].size();

        vector<vector<int>> vv(row, vector<int>(col,0));
        vv[0][0] = grid[0][0];

        for(int i = 1; i < row; i++)
           vv[i][0] = vv[i-1][0] + grid[i][0];
        
        for(int i = 1; i < col; i++)
           vv[0][i] = vv[0][i-1] + grid[0][i];

        for(int i = 1; i < row; i++)
        {
            for(int j = 1; j < col; j++)
            {
                vv[i][j] = min(vv[i-1][j], vv[i][j-1]) + grid[i][j];
            }
        }
        
        return vv[row-1][col-1];
    }
};
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

题目6-----背包问题

练码：背包问题2

这个背包问题你一定会有很多疑惑：
例如：放不放的下？ 放的下要不要放？
然后就是放的下，要不要遍历拿出某一个物品来比较价值。

核心：画图 + 感悟。
行标 i ： 物品个数
列标j ： 背包大小
数组下标表示什么呢？ 在背包大小为j的情况下，放i个物品的最大价值。

并且要多开一行一列： 表示没有物品的时候，或者背包大小为0的时候的价值 0 。
为什么要多开一行一列？？？ 解释困难-----> 需要感悟！！！！

代码：
时间复杂度：O（n * m）
空间复杂度： O（n * m）

class Solution {
public:
    int backPackII(int m, vector<int> &a, vector<int> &v)
    {
        int row = a.size() + 1;
        int col = m + 1;
        vector<vector<int>> vv(row,vector<int>(col,0));

        for(int i = 1; i < row; i++)
        {
            for(int j = 1; j < col; j++)
            {
                if(a[i-1] > j)
                {
                    vv[i][j] = vv[i-1][j];
                }
                else
                {
                    int take_pack = vv[i-1][j-a[i-1]] + v[i - 1];
                    vv[i][j] = max(take_pack, vv[i-1][j]);
                }
            }
        }
        return vv[row-1][col-1];
    }
};
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