流浪者与宝藏

1. 处理输入。
   题目中提到一个点可能有多个宝藏，但一个点只能取一个宝藏，显然同一个位置只需保留最大的那个宝藏。
   我们开一个500*500的数组作为地图 map。map记录点上最大宝藏的金币数。
2. 动态规划。

• 构建状态空间
  站在一个中间位置向后看，我们发现此时能影响到后续选择的因素只有两个，位置与手中剩余的钥匙数量，所以建立一个三维的dp数组，分别对应横坐标、纵坐标、钥匙剩余数量。
  所以我们的状态空间应该这样建：

  设f[i][j][t]，代表在（x,y）(1<=x<=i,1<=y<=j)范围内，剩余t把钥匙时所能获得的最大收益。

• 初始化
  显然处于起始位置时，无论如何，收益都是零，所以f[0][0][t]都设为0（鉴于大部分语言，新建数组后都默认初始化为0,所以也可不设置）

• 状态转移方程（感觉这一步做好，就成功80%了）*
  dp数组找好了，为f[i][j][t]，那么递推公式该怎么写呢？

  ab	ab	a
  ab	ab	a
  b	b

  
  当t固定时，f[i][j][t] 其实等于 身处区域a,或身处区域b,或身处右下角的小方格时的最大的收益。
  显然区域a的最大收益为f[i-1][j][t],区域b的最大收益为f[i][j-1][t]。
  那小方格的最大收益怎么算呢？

  c	c
  c	c

  
  
  题目说人只能往右下方跳，所以身处小方格时的前一步一定是在其左上角的c区域。当小方格没有宝藏时，那小方格的最大收益为c区域的收益即f[i-1][j-1][t]。当小方格有宝藏时，要么打开，要么不打开，取最大值即max(f[i-1][j-1][t],f[i-1][j-1][t+1]+map[i][j]);
  所以递推公式应该这样写：

  

• 构造最优解

  当我们写好一个i,j,t的循环后，就得到了整个地图的最大收益，f[max][max][t]。注意到并不是打开的宝藏越多收益就一定高的情况，我们还要遍历一遍t,返回其最大收益。

  
  

附上ac代码

import java.util.*;


public class Solution {
    /**
     * 流浪者与宝藏
     * @param n int整型 
     * @param k int整型 
     * @param x int整型一维数组 
     * @param y int整型一维数组 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int n, int k, int[] x, int[] y, int[] a) {
        // write code here
        int[][] map = new int[505][505];
        int row=0;int col=0;
        for(int i=0;i<n;i++){
            map[x[i]][y[i]]=Math.max(a[i],map[x[i]][y[i]]);
            row=Math.max(row,x[i]);
            col=Math.max(col,y[i]);
        }
        //优化空间
        int[][][] dp = new int[2][col+1][k+1];
        int cur=0,pre=1;
        for(int i=1;i<=row;i++){
            cur=1-cur;pre=1-pre;//滚动
            for(int j=1;j<=col;j++){
                for(int t=0;t<k;t++){
                    dp[cur][j][t]=max(dp[pre][j][t],dp[cur][j-1][t]); if(map[i][j]!=0)
                        dp[cur][j][t]=max(dp[cur][j][t],dp[pre][j-1][t+1]+map[i][j]);
                }
            }
        }
        int ans=0;
        for(int i=0;i<k;i++)ans=max(dp[cur][col][i],ans);
        return ans;
    }
    public int max(int a,int b){return a>b?a:b;}
}