动态规划例题及 Leetcode 题解

关于 DP

  • 动态规划是一门非常重要的算法,对它的掌握应该是计算机科学专业学生的基本功

  • 下面来把对这类算法的理解进行尽可能多的解释

  • 关键是 状态定义状态转移方程


最长递增子序列

给定K个整数的序列{ N1, N2, …, NK },其任意连续子序列可表示为{ Ni, Ni+1, …, Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序中元素和最大的一个, 例如给定序列{ -2, 11, -4, 13, -5, -2 },其最大连续子序列为{ 11, -4, 13 },最大和为20。

  • 定义sum[i]为’以A[i]作为最后一个结尾的连续子序列的最大值’

  • 状态转移方程为:sum[i]=max(sum[i-1]+a[i],a[i])

  • 实际求解的时候则是,只要sum>0,那么加上之后的a[i]都还是有可能使max增大的;但如果sum<0,则应该立即抛弃,从0开始计算下一个

a = {4, 8, -12, 3, 7, 9}
n = len(a)
sum = 0
max = 0
for i in range(n):
    sum += a[i]
    if sum > max:
        max = sum
    if sum < 0:
        sum = a[i]
return sum
public int LIS(int[] arr) {
        int i, j, max = 0;
        int n = arr.length;
        int[] list = new int[n]; // 存储长度
        Arrays.fill(list, 1);
        int[] index = new int[n]; // 存储距离
        Arrays.fill(index, -1);


        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++) {
                if (arr[i] > arr[j] && list[i] < list[j] + 1) {
                    list[i] = list[j] + 1;
                    index[i] = j;
                }
            }

        // 选择出最大的
        int max_index = 0;

        for (i = 0; i < n; i++)
            if (list[i] > max) {
                max = list[i];
                max_index = i;
            }


        StringBuilder builder = new StringBuilder();
        builder.insert(0, arr[max_index]);
        int next_index = index[max_index];
        while (next_index != -1) {
            builder.insert(0, arr[next_index] + " ");
            next_index = index[next_index];
        }
        System.out.println(builder.toString()); // 输出子序列
        return max;

数塔问题

img

要求从顶层到底层,每一层只能走到相邻节点,求经过的数字之和是多少

  • 定义状态方程:max[i,j] 表示以 [i,j] 作为起始点,所经过的最大的数字之和。则 max[1,1] 是我们要求的目标

  • 定义状态转移方程:max[i,j]=num[i,j]+max(max(i+1,j),max(i+1,j+1))

  • 接下来可以自底向上,也可以自顶向下,具体参见之前所写的关于hdu2084博文

#include<iostream>  
#include<cstring>  
using namespace std;  
#define maxnum 1000  
int num[maxnum][maxnum];  
int d[maxnum][maxnum];  
int main(void)  
{  
    int i,j,k;  
    int n,m;  
    cin>>n;  
    while(n--){  
        cin>>m;  
        for(i=1;i<=m;i++)  
            for(j=1;j<=i;j++)  
            cin>>num[i][j];  
        for(j=1;j<=m;j++) d[m][j]=num[m][j];  
  
        for(i=m-1;i>=1;i--)  
            for(j=1;j<=i;j++)  
            d[i][j]=num[i][j]+max(d[i+1][j+1],d[i+1][j]);  
        cout<<d[1][1]<<endl;  
        memset(d,0,sizeof(d));  
    }  
}  

背包问题

  • 有著名的背包问题九讲,这里自己先写最基本的

  • 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大

  • 如果单纯使用递归来求解 DP 的话有两种思路

public int Knapsack1(int[] value, int[] weight, int capacity, int number) {
        if (capacity <= 0 || number == 0)
            return 0;
        if (weight[number - 1] > capacity)
            return Knapsack1(value, weight, capacity, number - 1);
        else
            return max(value[number - 1] + Knapsack1(value, weight, capacity - weight[number - 1], number - 1),
                    Knapsack1(value, weight, capacity, number - 1));

    }

    public int Knapsack2(int[] value, int[] weight, int capacity, int index) {
        if (capacity <= 0 || index >= value.length)
            return 0;
        if (weight[index] > capacity)
            return Knapsack2(value, weight, capacity, index + 1);
        else
            return max(value[index] + Knapsack2(value, weight, capacity - weight[index], index + 1),
                    Knapsack2(value, weight, capacity, index + 1));
    }

        // KnapSack 问题,两种调用
        int[] value = {60, 100, 120};
        int[] weight = {10, 20, 30};
        int capacity = 50;
        int number = value.length;
        System.out.println(dp.Knapsack1(value, weight, capacity, number)); // 220
        int index = 0;
        System.out.println(dp.Knapsack2(value, weight, capacity, index));  // 220

Leetcode 上相关题目

303 Range Sum Quwey - Immutable
  • 链接

  • 大意:给出一个数组,要求返回任意两个区间范围的的值

  • 思路:题目中说到many calls to function,所以多次遍历求解肯定会TLE;而sum[i,j]=sum[j]-sum[i-1],所以一次遍历求出所有的sum值之后做减法就可以。注意要用全局变量

  • 代码:

// c++版
//用vector<int> 来存储状态会更好
class NumArray {
    int dp[100000];
public:
    NumArray(vector<int> &nums) {
        if (nums.empty())
            return ;
        int length=nums.size();
        memset(dp,0,sizeof(dp));
        dp[0]=nums[0];
        for(int i=1;i<length;i++)
            dp[i]=dp[i-1]+nums[i];
    }

    int sumRange(int i, int j) {
        if (i==0)
            return dp[j];
        else
            return dp[j]-dp[i-1];    
    }
};

python版:

class NumArray(object):
    def __init__(self, nums):
        
        self.dp = nums
        for i in range(1,len(nums)):
            self.dp[i] += self.dp[i-1]

    def sumRange(self, i, j):
        return self.dp[j] - (self.dp[i-1] if i > 0 else 0)

70 climbStatirs
  • 链接

  • 大意:登上一个楼梯,可以走1步,可以走两步,问走到n步有几种解法

  • 思路:用dp[n]来表示走到n步的方法数。对dp[n-1],只能选择走1步;对dp[n-2], 如果选择1+1,就会和dp[n-1]有重叠,只能选择2步

  • 代码: C++版:

class Solution {
public:
    int climbStairs(int n) {
        int dp[n]={0};
        dp[0]=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];
    }
};

python版:

class Solution(object):
    def __init__(self):
        self.dp={}
        
    def climbStairs(self, n):
        self.dp[1]=1
        self.dp[2]=2
        for i in range(3,n+1):
            self.dp[i]=self.dp[i-1]+self.dp[i-2]
        return self.dp[n]  

64 Minimum Path Sum
  • 链接

  • 大意:m*n的全为正数的矩阵,可以向右向下移动,求从左上到右下经过的距离之和最小值

  • 思路:动态规划,用dp[i][j]表示以i,j作为最后一个方块所经过的最短步数 则 dp[i][j]=max(dp[i-1][j]+grid[i][j],dp[i][j-1]+gird[i][j]

  • 代码: C++ 版:

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