思维导图

动态规划

动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程最优化的数学方法。它是20世纪50年代初美国数学家R.E.Bellman等人提出的最优化原理，它利用各阶段之间的关系，逐个求解，最终求得全局最优解。在设计动态规划算法时，需要确认原问题与子问题、动态规划状态、边界状态结值、状态转移方程等关键要素。在算法面试中，动态规划是最常考察的题型之一，大多数面试官都以可否较好的解决动态规划相关问题来区分候选是否聪明。

例1：爬楼梯（easy）

在爬楼梯时，每次可向上走1阶或2阶台阶，问有n阶楼梯有多少种上楼的方式？

• 算法思路

1、确认原问题与子问题：原问题是求n阶台阶所有走法的数量，子问题是求1阶台阶、2阶台阶...、n-1阶台阶的走法。
2、确认状态：本题的动态规划状态单一，第i个状态即为i阶台阶的所有走法数量。
3、确认边界状态的值：边界状态为1阶台阶与2阶台阶的走法。
4、确定状态转移方程：将求第i个状态的值转移为求第i-1个状态值与第i-2个状态的值。

• LeetCode 70.Climbing Stairs(回溯)

#include <stdio.h>

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1 || n == 2){
            return n;
        }
        return climbStairs(n-1) + climbStairs(n-2);
    }
};

int main(){
    Solution solve;
    printf("%d\n", solve.climbStairs(3));   
    return 0;
}

• LeetCode 70.Climbing Stairs

#include <stdio.h>
#include <vector>

class Solution {
public:
    int climbStairs(int n) {
        std::vector<int> dp(n + 3, 0);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

int main(){
    Solution solve;
    printf("%d\n", solve.climbStairs(3));   
    return 0;
}

例2：打家劫舍（easy）

在一条直线上，有n个房屋，每个房屋中有数量不等的财宝，盗贼希望从房屋中盗取财宝，如果同时从相邻的两个房屋中盗取财宝就会触发报警器。问在不触发报警器的前提下，最多可获取多少财宝？

• 算法思路

1、确认原问题与子问题：原问题为求n个房间的最优解，子问题为求前1个房间、前2个房间...、前n-1个房间的最优解。
2、确认状态：第 i 个状态即为前i个房间能够获得的最大财宝。
3、确认边界状态的值：前1个房间的最优解，前2个房间的最优解。
4、确定状态转移方程：① 选择第 i 个房间：第 i 个房间+前 i-2 个房间的最优解。② 不选择第 i 个房间：前 i-1 个房间的最优解。

• LeetCode 198.House Robber

#include <stdio.h>

#include <vector>
class Solution {
public:
    int rob(std::vector<int>& nums) {
        if (nums.size() == 0){
            return 0;
        }
        if (nums.size() == 1){
            return nums[0];
        }
        std::vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        dp[1] = std::max(nums[0], nums[1]);
        for (int i = 2; i < nums.size(); i++){
            dp[i] = std::max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[nums.size() - 1];
    }
};

int main(){
    Solution solve;
    std::vector<int> nums;
    nums.push_back(5);
    nums.push_back(2);
    nums.push_back(6);
    nums.push_back(3);
    nums.push_back(1);
    nums.push_back(7);  
    printf("%d\n", solve.rob(nums));
    return 0;
}

例3：最大字段和（easy）

给定一个数组，求这个数组的连续子数组中，最大的那一段的和。
数组如：[-2，1，-3，4，-1，2，1，-5，4]
连续子数组如：[-2，1]、[1，-3，4，-1]、...、[-2，1，-3，4，-1，2，1，-5，4]
和最大的连续子数组是：[4，-1，2，1]，为 6。

• 算法思路

将求n个数的数组的最大子段和，转换为分别求出以第1个、第2个、…第i个、…第n个数字结尾的最大字段和，再找出这个结果中最大的，即为结果。

• LeetCode 53.Maximum Subarray

#include <stdio.h>

#include <vector>
class Solution {
public:
    int maxSubArray(std::vector<int>& nums) {
        std::vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        int max_res = dp[0];
        for (int i = 1; i < nums.size(); i++){
            dp[i] = std::max(dp[i-1] + nums[i], nums[i]);
            if (max_res < dp[i]){
                max_res = dp[i];
            }
        }
        return max_res;
    }
};

int main(){
    Solution solve;
    std::vector<int> nums;
    nums.push_back(-2);
    nums.push_back(1);
    nums.push_back(-3);
    nums.push_back(4);
    nums.push_back(-1);
    nums.push_back(2);
    nums.push_back(1);
    nums.push_back(-5);
    nums.push_back(4);
    printf("%d\n", solve.maxSubArray(nums));
    return 0;
}

例4：找零钱（medium）

已知不同面值的钞票，求如何用最少数量的钞票组成某个金额，求可以使用的最少钞票数量。如果任意数量的已知面值钞票都无法组成该金额，则返回-1
例如：钞票面值：[2]；金额：3；无法组成，返回-1。
钞票面值：[1，2，5]；金额：11=5+5+1；需要3张。
钞票面值：[1，2，5，7，10]；金额：14=7+7；需要2张。

• 算法思路

• LeetCode 322.Coin Change

#include <stdio.h>

#include <vector>

class Solution {
public:
    int coinChange(std::vector<int>& coins, int amount) {
        std::vector<int> dp;
        for (int i = 0; i <= amount; i++){
            dp.push_back(-1);
        }
        dp[0] = 0;
        for (int i = 1; i <= amount; i++){
            for (int j = 0; j < coins.size(); j++){
                if (i - coins[j] >= 0 && dp[i - coins[j]] != -1){
                    if (dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1){
                        dp[i] = dp[i - coins[j]] + 1;
                    }
                }
            }
        }
        return dp[amount];
    }
};

int main(){ 
    Solution solve;
    std::vector<int> coins;
    coins.push_back(1);
    coins.push_back(2);
    coins.push_back(5);
    coins.push_back(7);
    coins.push_back(10);    
    for (int i = 1; i<= 14; i++){
        printf("dp[%d] = %d\n", i, solve.coinChange(coins, i));
    }
    return 0;
}

例5：三角形（medium）

给定一个二维数组，其保存了一个数字三角形，求从数字三角形页端到底端各数字和最小的路径之和，每次可以向下走相邻的两个位置。

• 算法思路

• LeetCode 120.Triangle

#include <stdio.h>

#include <vector>

class Solution {
public:
    int minimumTotal(std::vector<std::vector<int> >& triangle){
        if (triangle.size() == 0){
            return 0;
        }
        std::vector<std::vector<int> > dp;
        for (int i = 0; i < triangle.size(); i++){
            dp.push_back(std::vector<int>());
            for (int j = 0; j < triangle.size(); j++){
                dp[i].push_back(0);
            }
        }
        for (int i = 0; i < dp.size(); i++){
            dp[dp.size()-1][i] = triangle[dp.size()-1][i];
        }
        for (int i = dp.size() - 2; i >= 0; i--){
            for (int j = 0; j < dp[i].size(); j++)
                dp[i][j] = std::min(dp[i+1][j], dp[i+1][j+1])
                             + triangle[i][j];
        }
        return dp[0][0];
    }
};

int main(){
    std::vector<std::vector<int> > triangle;
    int test[][10] = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
    for (int i = 0; i < 4; i++){
        triangle.push_back(std::vector<int>());
        for (int j = 0; j < i + 1; j++){
            triangle[i].push_back(test[i][j]);
        }
    }
    Solution solve;
    printf("%d\n", solve.minimumTotal(triangle));
    return 0;
}

例6：最长上升子序列（hard）

已知一个未排序数组，求这个数组最长上升子序列的长度。例如：[1，3，2，3，1，4]，其中有很多上升子序列，如[1，3]、[1，2，3]、[1，2，3，4]等，其中最长的上升子序列长度为4，分别考虑O（n^2）与O（nlogn）两种复杂度算法。

• 算法思路 - 1

• LeetCode 300.Longest Increasing Subsequence(solve1)

#include <stdio.h>

#include <vector>

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        if (nums.size() == 0){
            return 0;
        }
        std::vector<int> dp(nums.size(), 0);
        dp[0] = 1;
        int LIS = 1;
        for (int i = 1; i < dp.size(); i++){
            dp[i] = 1;
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j] && dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                }
            }
            if (LIS < dp[i]){
                LIS = dp[i];
            }
        }
        return LIS;
    }
};

int main(){
    int test[] = {10, 9, 2, 5, 3, 7, 101, 18};
    std::vector<int> nums;
    for (int i = 0; i < 8; i++){
        nums.push_back(test[i]);
    }
    Solution solve;
    printf("%d\n", solve.lengthOfLIS(nums));
    return 0;
}

• 算法思路 - 2

设置一个栈（使用vector实现）stack，stack[i]代表长度为i+1的上升子序列最后一个元素的最小可能取值，即若要组成长度为i+2的上升子序列，需要一个大于stack[i]的元素。最终栈的大小，即为最长上升子序列长度。

• LeetCode 300.Longest Increasing Subsequence(n^2)

#include <stdio.h>

#include <vector>

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        if (nums.size() == 0){
            return 0;
        }
        std::vector<int> stack;
        stack.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++){
            if (nums[i] > stack.back()){
                stack.push_back(nums[i]);
            }
            else{
                for (int j = 0; j < stack.size(); j++){
                    if (stack[j] >= nums[i]){
                        stack[j] = nums[i];
                        break;
                    }
                }
            }
        }
        return stack.size();
    }
};

int main(){
    int test[] = {1, 3, 2, 3, 1, 4};
    std::vector<int> nums;
    for (int i = 0; i < 6; i++){
        nums.push_back(test[i]);
    }
    Solution solve;
    printf("%d\n", solve.lengthOfLIS(nums));
    return 0;
}

• LeetCode 300.Longest Increasing Subsequence(nlogn)

#include <stdio.h>

#include <vector>

int binary_search(std::vector<int> nums, int target){
    int index = -1;
    int begin = 0;
    int end = nums.size() - 1;
    while (index == -1){
        int mid = (begin + end) / 2;
        if (target == nums[mid]){
            index = mid;
        }
        else if (target < nums[mid]){
            if (mid == 0 || target > nums[mid - 1]){
                index = mid;
            }
            end = mid - 1;
        }
        else if (target > nums[mid]){
            if (mid == nums.size() - 1 || target < nums[mid + 1]){
                index = mid + 1;
            }
            begin = mid + 1;
        }
    }
    return index;
}

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        if (nums.size() == 0){
            return 0;
        }
        std::vector<int> stack;
        stack.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++){
            if (nums[i] > stack.back()){
                stack.push_back(nums[i]);
            }
            else{
                int pos = binary_search(stack, nums[i]);
                stack[pos] = nums[i];
            }
        }
        return stack.size();
    }
};

int main(){
    int test[] = {1, 3, 2, 3, 1, 4};
    std::vector<int> nums;
    for (int i = 0; i < 6; i++){
        nums.push_back(test[i]);
    }
    Solution solve;
    printf("%d\n", solve.lengthOfLIS(nums));
    return 0;
}

例7：最小路径和（medium）

已知一个二维数组，其中存储了非负整数，找到从左上角到右下角的一条路径，使得路径上的和最小。（移动过程中只能向下或向右）

• 算法思路

• LeetCode 64.Minimum Path Sum

#include <stdio.h>

#include <vector>

class Solution {
public:
    int minPathSum(std::vector<std::vector<int> >& grid) {
        if (grid.size() == 0){
            return 0;
        }
        int row = grid.size();
        int column = grid[0].size();
        std::vector<std::vector<int> > 
                        dp(row, std::vector<int>(column, 0));
        
        dp[0][0] = grid[0][0];
        for (int i = 1; i < column; i++){
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        for (int i = 1; i < row; i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
            for (int j = 1; j < column; j++){
                dp[i][j] = std::min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[row-1][column-1];
    }
};

int main(){
    int test[][3] = {{1,3,1}, {1,5,1}, {4,2,1}};
    std::vector<std::vector<int> > grid;
    for (int i = 0; i < 3; i++){
        grid.push_back(std::vector<int>());
        for (int j = 0; j < 3; j++){
            grid[i].push_back(test[i][j]);
        }
    }
    Solution solve;
    printf("%d\n", solve.minPathSum(grid)); 
    return 0;
}

例8：地牢游戏（hard）

已知一个二维数组，左上角代表骑士的位置，右下角代表公主的位置，二维数组中存储整数，正数可以给骑士增加生命值，负数会减少骑士的生命值，问骑士初始时至少是多少生命值，才可保证骑士在行走的过程中至少保持生命值为1。（骑士只能向下或向右行走）

• 算法思路

• LeetCode 174.Dungeon Game

#include <stdio.h>

#include <vector>

class Solution {
public:
    int calculateMinimumHP(std::vector<std::vector<int> >& dungeon) {
        if (dungeon.size() == 0){
            return 0;
        }
        std::vector<std::vector<int> > 
            dp(dungeon.size(), std::vector<int>(dungeon[0].size(), 0));
        int row = dungeon.size();
        int column = dungeon[0].size();
        dp[row-1][column-1] = std::max(1, 1-dungeon[row-1][column-1]);
        for (int i = column-2; i>=0; i--){
            dp[row-1][i] = std::max(1,
                                    dp[row-1][i+1] - dungeon[row-1][i]);
        }
        for (int i = row-2; i>=0; i--){
            dp[i][column-1] = std::max(1,
                                dp[i+1][column-1] - dungeon[i][column-1]);
        }
        for (int i = row-2; i>=0; i--){
            for (int j = column-2; j>=0; j--){
                int dp_min = std::min(dp[i+1][j], dp[i][j+1]);
                dp[i][j] = std::max(1, dp_min - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
};

int main(){
    int test[][3] = {{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}};
    std::vector<std::vector<int> > dungeon;
    for (int i = 0; i < 3; i++){
        dungeon.push_back(std::vector<int>());
        for (int j = 0; j < 3; j++){
            dungeon[i].push_back(test[i][j]);
        }
    }
    Solution solve;
    printf("%d\n", solve.calculateMinimumHP(dungeon));
    return 0;
}