动态规划算法OJ刷题(1)

动态规划Dynamic Programming

简称DP，有以下3个特点：1、把原来的问题分解成了几个相似的子问题；2、所有的子问题都只需要解决一次；3、储存子问题的解。

不同于递归，递归中子问题的解是不保存的，是通过函数栈帧传递的。

状态和转移方程就是指子问题和子问题之间的递推关系。

动态规划问题一般从以下四个角度考虑：1、状态定义（抽象出子问题）；2、状态间的转移方程定义（递推关系）；3、状态的初始化（即初始子问题）；4、返回结果（通常是某几个状态的返回值）。定义的状态一定要形成递推关系。

动态规划的本质，是对问题状态的定义和状态转移方程的定义(状态以及状态之间的递推关系)。

适用场景：最大值/最小值, 可不可行, 是不是，方案个数。

JZ10 斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

解题思路

1、递归

根据函数表达式可以写出代码

class Solution {
public:
    int Fibonacci(int n) {
        if(0 == n)
            return 0;
        if(n == 1 && 2 == n)
            return 1;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
};
1
2
3
4
5
6
7
8
9
10

时间复杂度会比较大，以指数级增长。

2、动规解法

时间复杂度O(N)

• 状态F(i)：第i项的值；
• 返回结果：第n项斐波那契数F(n)；
• 状态转移方程：F(i) = F(i-1) + F(i-2)；
• 初始状态：F(0) = 0, F(1) = 1

总共有n+1项，从第0项开始算。那么就要创建n+1大小的数组来保存中间状态的值

//空间复杂度O(N)
class Solution {
public:
    int Fibonacci(int n) {
        //创建一个数组，用于保存中间状态的解
        int* F = new int[n + 1];
        //初始化F[0] F[1]
        F[0] = 0;//f(0)
        F[1] = 1;//f(1)
        //状态转移方程
        for(int i = 2; i <= n; i++)
        {
            F[i] = F[i-1] + F[i-2];
        }
        return F[n];
    }
};
---------------优化---------------
//空间复杂度O(1)
class Solution {
public:
    int Fibonacci(int n) {
        int fn = 0;
        int fn1 = 1;//f(n-1)--f(1)
        int fn2 = 0;//f(n-2)--f(0)

        for(int i = 2; i <= n; i++)
        {
            //f(n) = f(n-1) + f(n-2)
            fn = fn1 + fn2;
            //f(n-2) -> f(n-1) -> f(n)
            fn2 = fn1;
            fn1 = fn;
        }
        return fn;
    }
};
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
34
35
36
37

CC12 拆分词句

题目描述

给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。

解题思路

1、动规解法

问题：字符串s是否能被成功分割 --> 抽象状态

• 状态F(i)： 前i个字符是否能根据dict中的词分割；

• 状态递推：j < i && F(j) && substr[j+1, i]能否在词典中找到

  F(i)： true{j < i && F(j) && substr[j+1, i]能在词典中找到} OR false； 在j < i中，只要能找到一个F(j) == true，并且从j+1到i之间的字符能在词典中找到，则F(i) == true；

• 初始值F(0) = true： 对于初始值无法确定的，可以引入一个不代表实际意义的空状态，作为状态的起始空状态的值需要保证状态递推可以正确且顺利的进行，到底取什么值可以通过简单的例子进行验证；

• 返回结果F(字符串长度)

比如s = “leetcode”， dict = [“leet”, “code”]。

F(8) : F(0) && [0, 8]
	   F(1) && [2, 8]
       F(2) && [3, 8]
       F(3) && [4, 8]
       F(4) && [5, 8] -> F(0) && [0,4] + F(1) && [1,3]+...//要求true == F(0) && [0,4], 故设F(0)==true
       F(5) && [6, 8]
       F(6) && [7, 8]
       F(7) && [8, 8]
1
2
3
4
5
6
7
8

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        //状态结果返回
        vector<bool> canBreak(s.size() + 1, false);
        //初始状态
        canBreak[0] = true;
        //状态转移方程
        for(int i = 1; i <= s.size(); i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(canBreak[j] && (dict.find(s.substr(j, i - j)) != dict.end()))
                    canBreak[i] = true;
            }
        }
        return canBreak[s.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

CC31 三角形

题目描述

给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字。如[[20],[30,40],[60,50,70],[40,10,80,30]]，最小的从顶部到底部的路径和是20 + 30 + 50 + 10 = 110。

解题思路

1、动规解法

即[0][0]是必走的，要走到最后一行才算把一条路径走完。

求第i行的最短路径，就是求第i-1行的最短路径+本行的一个数字。

• 状态：

  子状态：从(0, 0)到(1, 0), (1, 1), (2, 0), … (n, n)的最短路径和

  F(i,j): 从(0, 0)到(i, j)的最短路径和

• 状态递推：

  F(i,j) = min( F(i-1, j-1), F(i-1, j) ) + triangle[i][j]。需要对j=0的情况做处理，以及i=j的情况也要做处理（即j=0和i==j的边界点都只有一条路径）

• 初始值：

  F(0,0) = triangle[0][0]

• 返回结果：

  min(F(n-1, i))

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        if(triangle.empty()) return 0;
        //初始值
        vector<vector<int>> min_sum(triangle);//初始化F[0][0]
        //状态递推
        int line = triangle.size();
        for(int i = 1; i < line; i++)//从第1行开始走，走到最后一行才算走完
        {
            for(int j = 0; j <= i; j++)
            {
                if(j == 0) min_sum[i][j] = min_sum[i-1][j];
                else if(i == j) min_sum[i][j] = min_sum[i-1][j-1];
                else min_sum[i][j] = min(min_sum[i-1][j-1], min_sum[i-1][j]);
                //递推方程
                min_sum[i][j] = min_sum[i][j] + triangle[i][j];
            }
        }
        //返回结果 min(F(n-1, i))
        int result = min_sum[line - 1][0];
        for(int i = 1; i < line; i++)
        {
            result = min(min_sum[line-1][i], result);
        }
        return result;
    }
};
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