前言：最近刷剑指offer刷到了动态规划相关的问题，之前没怎么学过，所以特地抽一天时间来学一下，以下为学习的笔记

动态规划

题目类型

1. 计数：
有多少种方式走到右下角
有多少种方法选出k个数使得和为Sum
2. 求最大最小值：
从左上角走到右下角路径的最大数字和
最长上升子序列长度
3. 求存在性：
取石子游戏，先手是否必胜
能不能选出k个数使得和是Sum

解题步骤

  1. 确定状态
    简单的说，就是解动态规划时需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么，类似解数学题中，xyz代表什么一样，具体分为下面两个步骤：
    • 研究最优策略的最后一步
    • 化为子问题
  2. 转移方程
    根据子问题定义直接得到
  3. 初始条件和边界情况
    初始条件一般都是a[0]、a[1]这种，多看看
    边界条件主要是看数组的边界，数组越不越界
  4. 计算顺序
    大部分从小到大迭代，精髓在于使用之前计算得到的结果

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0
示例 4：

输入：coins = [1], amount = 1
输出：1
示例 5：

输入：coins = [1], amount = 2
输出：2

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

思路与题解

代码

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
/*
    最后一步：添加一个硬币组成当前的金额，前面几步已经得到最优解
    转移方程：F[amount] = min{F[amount-coins]}
    边界条件：1. F[0] = 0; 2.负数硬币为正无穷
*/

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int* F = new int[amount+1];
        int N = coins.size();
        
        F[0] = 0;

        int i,j;
        for(i = 1;i <= amount;i++)
        {
            F[i] = INT_MAX;
            for(j = 0;j < N; j++)
            { 
                if( i-coins[j] >= 0 && F[i-coins[j]]!= INT_MAX)
                {
                     F[i] = min(F[i-coins[j]] + 1 ,F[i]);
                }
            }
        }

        if(F[amount] == INT_MAX) F[amount] = -1;

        return F[amount];
    }
};

62. 不同路径

难度 中等

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

img

1
2
输入：m = 3, n = 7
输出：28

示例 2：

1
2
3
4
5
6
7
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

1
2
输入：m = 7, n = 3
输出：28

示例 4：

1
2
输入：m = 3, n = 3
输出：6

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

思路与题解

转移方程：$F[i][j] = F[i-1][j] + F[i][j-1];$

初始状态：$F[i][0]=1;F[0][j] = 1$

代码

C++二维数组开辟方法

这里还学到了点C++的二维数组的开辟方法，以开辟m行，n列的二维数组 array2D[m][n]

方法总结如下：

  1. n为已知常量；二维数组开辟时第二位不能为变量，因此需要n已知且为常量才能使用
    假设 n = 5;则可开辟array2D[m][5]

  2. 使用指针间接引用；即先开辟 m 个指向指针的指针`array2D再在每一行开辟新的行数组

1
2
3
4
5
int **array2D = new int *[m];  
for(i = 0; i < m; i++)  
{  
array2D[i] = new int[n];  
}
  1. 使用STL中的vector容器
1
2
3
4
5
6
7
8
9
10
11
12
typedef std::vector<int>  IntVector;  
typedef std::vector<IntVector>    IntVector2D;  
unsigned int i, j;  

IntVector2D *pArray2D = new IntVector2D;  

// 动态设置大小.  
pArray2D->resize(height);  
for(i=0; i<height; ++i)  
{  
    (*pArray2D)[i].resize(width);  
}

解题代码

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
/*
    转移方程：F[i][j] = F[i-1][j] + F[i][j-1];
*/

class Solution {
public:
    int uniquePaths(int m, int n) {
        int i,j;
        int **F = new int*[m];
        for(i = 0;i < m; i++ )
            F[i] = new int[n];
        

        for( i = 0;i < m;i++ )
        {
            for( j = 0;j < n;j++)
            {
                if(i == 0 || j == 0) F[i][j] = 1;
                else F[i][j] = F[i-1][j] + F[i][j-1];
            }
        }
    
    return F[m-1][n-1];
    }
};

55. 跳跃游戏

难度 中等

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

  • 1 <= nums.length <= 3 * 104
  • 0 <= nums[i] <= 105

思路

其实这题并不适合拿动态规划来解，因为写出来的时间复杂度有$O(n^2)$数量级（所以我的题解在LeetCode里因为超时挂了。。。不过还是作为一个DP的典型题目写下思路

代码

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
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int i,j,Size;
        Size = nums.size();
        bool *F = new bool[Size];

        F[0] = true;

        for(i = 1; i < Size; i++)
        {
            F[i] = false;
            for(j = 0;j < i;j++)
            {
                if(F[j] && nums[j] + j >= i)
                {
                    F[i] = true;
                    break;
                }
            }
        }

        return F[Size-1];
    }
};