动态规划Java解题

解题思路:动态规划的简单应用

注意事项:最好得拿张纸写写，再用断点去一点点领悟其运行过程

参考代码:

/*
   关于动态规划的一道题目
   一个美食家在一条街上从前往后吃，每一次吃的都要比上次的更加好
   要尽量吃的次数多
   会输入总的小吃的数目以及小吃的美味程度

   Time:2023/2/10

   Author:Cherish

   c1557
*/

import java.util.Arrays;
import java.util.Scanner;

public class Main {
   public static void main(String[] args) {
       int SnackSum;
       int maxDelicious = 0;        //最大美味次数
       int i,j;
       Scanner ss = new Scanner(System.in);
       SnackSum = ss.nextInt();
       int[] SnackDelicacy = new int[SnackSum];
       int[] dp = new int[SnackSum];
       for (i = 0; i < SnackSum; i++){
           SnackDelicacy[i] = ss.nextInt();
       }
       /*
           思路是动态规划，建议拿张纸画图
           最好再用断点试着判断一下才行
           不然比较难理解
        */
       Arrays.fill(dp,1);

        //---以下是重点---
       for (i = 1; i <= SnackSum-1; i++){
           for (j = i - 1; j >= 0; j--){
               if (SnackDelicacy[i] >= SnackDelicacy[j]){
                   dp[i] = Math.max(dp[i], dp[j]+1);
               }
           }
           if (dp[i] > maxDelicious){
               maxDelicious = dp[i];
           }
       }

        //---到此为止---
       System.out.println(maxDelicious);
       // 测试输入情况
       // System.out.println(SnackSum);
       // System.out.println(Arrays.toString(SnackDelicacy));
   }
}