动态规划——接金币

问题：

小赛非常喜欢玩游戏，最近喜欢上了一个接金币的游戏。在游戏中，使用帽子左右移动接金币，金币接的越多越好，但是金币掉到地上就不能再接了。为了方便问题的描述，我们把电脑屏幕分成11格，帽子每次能左右移动一格。现在给电脑屏幕如图标上坐标：

也就是说在游戏里，金币都掉落在0-10这11个位置。开始时帽子刚开始在5这个位置，因此在第一秒，帽子只能接到4,5,6这三个位置中其中一个位置上的金币。问小赛在游戏中最多可能接到多少个金币？（假设帽子可以容纳无穷多个金币）

输入

输入数据有多组。每组数据的第一行为以正整数n (0＜n＜100000)，表示有n个金币掉在屏幕上上。在结下来的n行中，每行有两个整数x,T (0＜T＜100000),表示在第T秒有一个金币掉在x点上。同一秒钟在同一点上可能掉下多个金币。n=0时输入结束。输入数据以空格隔开
————————————————
版权声明：本文为CSDN博主「yong_zi」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/yong_zi/article/details/81612858

解决：使用动态规划，从后往前累加

（1）边界情况：下一次只有两次移动位置

（2）其他情况：有两次移动情况

（3）比较后取大

（4）分析图形可知可以转换为图为题：

code：

package yrc4;

import java.util.Scanner;
/*
动态规划实现
 */
public class Main16_3 {
    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        int n;
        int dp[][];
        while(s.hasNext()) {
            //横坐标为位置，纵坐标为时间(时间最大为10000)
            dp = new int[11][100000];
            n = s.nextInt();
            int x,t,max=0;
            //根据输入初始化二维数组
            for(int i=0;i<n;i++) {
                x = s.nextInt();
                t = s.nextInt();
                max = t>max?t:max;
                dp[x][t]++;
            }
            //开始进行动态规划计算
            for(int i=max-1;i>=0;i--) {
                for(int j=0;j<11;j++) {
                    //处理边界情况
                    if(j==0) {
                        dp[j][i] += Math.max(dp[j][i+1], dp[j+1][i+1]);
                    }else if(j==10) {
                        dp[j][i] += Math.max(dp[j][i+1], dp[j-1][i+1]);
                    }else {
                        dp[j][i] += Math.max(dp[j][i+1], Math.max(dp[j-1][i+1], dp[j+1][i+1]));
                    }
                }
            }
            //因为初始位置为5，所以直接输出（5,0）
            System.out.println(dp[5][0]);
        }
        s.close();
        
    }

}