竞赛算法–动态规划 经典例题详解

  • 动态规划方法代表了这一类问题(最优子结构or子问题最优性)的一般解法,是设计方法或策略,不是具体算法
  • 本质是递推,核心是找到状态转移方程,写出DP方程

形式:

  • 记忆型递推
  • 递推

举例:

  • 01背包问题
    钢条切割问题
    数字三角形问题(滚动数组)
    最长公共子序列问题
    完全背包问题
    最长上升子序列问题
1.1 、 01背包问题
题目描述:

在这里插入图片描述

题目分析:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
         // TODO Auto-generated method stub
          Scanner in = new Scanner(System.in);
   int n = in.nextInt();
   int v = in.nextInt();
   int []arrv = new int [n+1];
   int []arrw = new int [n+1];
   for(int i=1;i<=n;i++) {
       arrv[i]=in.nextInt();
       arrw[i]=in.nextInt();
           }
   int [][] re = new int [n+1][v+1];
   for(int i=1;i<=n;i++) {
           for(int j=1;j<=v;j++) {
     // not select i goods
     re[i][j]=re[i-1][j];
     // select i goods 
            if(j>=arrv[i]) {
                re[i][j]=Math.max(re[i-1][j-arrv[i]]+arrw[i],re[i][j] );
            }
        }
           }
     System.out.println(re[n][v]);   
     }
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

1.3 、 数字三角形问题(滚动数组)

题目描述:原题链接
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

import java.util.*;
public class Main436{
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        int row = in.nextInt();
        int[][] a = new int[row][row];
        for(int i=0;i<row;i++){
            for(int j=0;j<=i;j++){
                a[i][j]=in.nextInt();
            }
        }
        System.out.println(dp(a,row));
    }
    public static int dp(int[][] a ,int row) {
     int rows = row;      // 行数
     int columns = row ; // 列数(最后一行)
     int[] result = new int [columns];
     for(int k=0;k<rows;k++) {
          result[k]=a[rows-1][k];
     }
     for(int i=row-2;i>=0;i--){
          for(int j=0;j<=i;j++){
               result[j] = a[i][j]+Math.max(result[j], result[j+1]);
          }
       }
     return result[0];
    }
}