首页 > 代码库 > 动态规划 选择硬币使得价值最大
动态规划 选择硬币使得价值最大
动态规划
第一个人每次都选择 当前+之后可以拿到的 最大的值
当第一个人选择完成后,第二个人用同样的策略拿剩下的硬币中 当前+之后可以拿到的 最大的值
用dp[i][j]记录在还剩v[i]~v[j]时,先拿的人可以最多拿多少钱
用record[i][j]记录在还剩v[i]~v[j]时,先拿的人选择了哪一个 只有i和j两种可能
当只剩1个硬币的时候: dp[i][i] = v[i] //只能拿这个,无悬念
当只剩2个硬币的时候: dp[i][i + 1] = max(v[i], v[i + 1]) //一定选最大的
当剩余硬币>=3个时,需要知道第二个人的策略: dp[i][j] = max(拿第一个 + 第二个人选择后剩下的能够拿到的最大值, 拿最后一个 + 第二个人选择后剩下的能够拿到的最大值)
public static int maxValue(int[]v,int n){ int[][] dp = new int[n][n];//记录i-j中可以选择的最大值 int[][] record = new int[n][n];//记录 i-j中,使得选择的结果最大的 那个 选中值的位置 for(int i=0;i<n;i++){ dp[i][i]=v[i]; record[i][i]=i; } for(int i=2;i<=n;i++){// 当前剩余硬币数量的遍历!!!!从两个开始,3,4,,,,直到长度n。 for(int s=0;(s+i)<=n;s++){//起始位置遍历 int e=i+s-1; //当前结束为止 int num1=v[s],num2=v[e];//首、尾的值 if(i>=3){// 长度超过2时,需要考虑剩余硬币中能拿到的钱数 //假设拿第一个 if(record[s+1][e]==s+1)//第二个人会拿剩余的里面的第一个 num1+=dp[s+2][e]; else// 第二个人会拿剩余的里面的最后一个 num1 +=dp[s+1][e-1]; //假设拿最后一个 if(record[s][e-1]==s)//同上 num2 += dp[s+1][e-1]; else //同上 num2 +=dp[s][e-2]; } record[s][e]=(num1>num2)?s:e;//长度为i的选择中,选择综合值大的那个,做为选取目标 dp[s][e]=(num1>num2)?num1:num2;// } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ System.out.print(dp[i][j]+" "); } System.out.println(); } return dp[0][n-1]; }
动态规划 选择硬币使得价值最大
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。