import java.util.HashMap;class Point {int x;int y;Point() { x = 0; y = 0; }Point(int a, int b) { x = a; y = b; }}public class Solution {//解法一:存在问题public int maxPoints(Point[] points) {if(points==nu
174. 地下城游戏https://leetcode.cn/problems/dungeon-game/description/ 恶魔们抓住了公主并将她关在了地下城dungeon的右下角。地下城是由m x n个房间组成的二维网格。我们英勇的骑士最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至0或以下,他会立即死亡
一、题目: 把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。 二、思路和代码: DP:使用上一次的结果推出下一次的,而第一次的朝上一面的点数之和出现的概率是很清晰的,都是它本身1次/6种; 第一个骰子(初始化结果): 第二个:
动态规划 思路: 选择元素 x,获得其点数,删除 x + 1 和 x - 1,则其他的 x 的点数也会被获得;可以将数组转换成一个有序 map,key 为 x, value 为对应所有 x 的和;则问题转换成了不能同时获得相邻两个房间的金币并能获得最大收益问题:力扣198. 打家劫舍;动态规划状态转移方程 dp[i] 跟之前两个状态相关,可以使用滚动数组的方式,减少空间复杂度: dp[i] =