剑指offer—动态规划-爱代码爱编程
题目代号: 剑指 Offer 46. 把数字翻译成字符串
题目描述:
给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
测试用例:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译,分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”
我的分析:
代码:
public int translateNum(int num) {
String s = String.valueOf(num);
int[] dp = new int[s.length()+1];//数组最后一位下标是s.length()
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= s.length(); i ++){//所以这里的截至数字一定是s.length()
String temp = s.substring(i-2, i);//i-2 <= 位数 < i (这个的意思包括i-2 i-1两位数)
if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0)
dp[i] = dp[i-1] + dp[i-2];//当这个两位数可以被翻译
else
dp[i] = dp[i-1];//当这个两位数不可以被翻译
}
return dp[s.length()];
}
题目代号: 剑指 Offer 47. 礼物的最大价值
题目描述:
在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
测试用例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
我的分析:
就每个点去看它的来源,就是左或者上,看左和上哪个大,就取哪个
代码:
public int maxValue(int[][] grid) {
int m = grid.length, n = grid[0].length;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0 && j == 0) continue;//初始值肯定就是继续遍历了
if(i == 0) grid[i][j] += grid[i][j - 1] ;//在边界的时候很容易理解,来源只有一个
else if(j == 0) grid[i][j] += grid[i - 1][j];
else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);//既然只向右下走,那无论哪个位置,来源总是左上
}
}
return grid[m - 1][n - 1];
}
题目代号: 剑指 Offer 60. n个骰子的点数
题目描述:
把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
测试用例:
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
我的分析:
第一个for:依次增加后面的节点数(3 4 5 6 7)
第二个for:前 i-1 个点数之和(前2个)
第三个for:当前这个节点 i 加进去的影响(第3个进去能带来什么影响)
代码:
public double[] dicesProbability(int n) {
//因为最后的结果只与前一个动态转移数组有关,所以这里只需要设置一个一维的动态转移数组
//原本dp[i][j]表示的是前i个骰子的点数之和为j的概率,现在只需要最后的状态的数组,所以就只用一个一维数组dp[j]表示n个骰子下每个结果的概率。
//初始是1个骰子情况下的点数之和情况,就只有6个结果,所以用dp的初始化的size是6个
double[] dp = new double[6];
//只有一个数组
Arrays.fill(dp,1.0/6.0);
//从第2个骰子开始,这里n表示n个骰子,先从第二个的情况算起,然后再逐步求3个、4个···n个的情况
//i表示当总共i个骰子时的结果
for(int i=2;i<=n;i++){
//每次的点数之和范围会有点变化,点数之和的值最大是i*6,最小是i*1,i之前的结果值是不会出现的;
//比如i=3个骰子时,最小就是3了,不可能是2和1,所以点数之和的值的个数是6*i-(i-1),化简:5*i+1(只减去前几个)
//当有i个骰子时的点数之和的值数组先假定是temp
double[] temp = new double[5*i+1];
//从i-1个骰子的点数之和的值数组入手,计算i个骰子的点数之和数组的值
//先拿i-1个骰子的点数之和数组的第j个值,它所影响的是i个骰子时的temp[j+k]的值
for(int j=0;j<dp.length;j++){
//比如只有1个骰子时,dp[1]是代表当骰子点数之和为2时的概率,它会对当有2个骰子时的点数之和为3、4、5、6、7、8产生影响,因为当有一个骰子的值为2时,另一个骰子的值可以为1~6,产生的点数之和相应的就是3~8;比如dp[2]代表点数之和为3,它会对有2个骰子时的点数之和为4、5、6、7、8、9产生影响;所以k在这里就是对应着第i个骰子出现时可能出现六种情况,这里可能画一个K神那样的动态规划逆推的图就好理解很多
for(int k=0;k<6;k++){
//这里记得是加上dp数组值与1/6的乘积,1/6是第i个骰子投出某个值的概率
temp[j+k]+=dp[j]*(1.0/6.0);
}
}
//i个骰子的点数之和全都算出来后,要将temp数组移交给dp数组,dp数组就会代表i个骰子时的可能出现的点数之和的概率;用于计算i+1个骰子时的点数之和的概率
dp = temp;
}
return dp;
}