算法笔记——动态规划
2020-04-14 本文已影响0人
yaco
- 记几道典型的动态规划，分析思路
换钱的方法数
问题描述
给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求换钱有多少种方法。
【举例】
arr=[5,10,25,1]，aim=0。组成0元的方法有1种，就是所有面值的货币都不用。所以返回1。
arr=[5,10,25,1]，aim=15。组成15元的方法有6种，分别为3张5元、1张10元+1张5元、1张10元+5张1元、10张1元+1张5元、2张5元+5张1元和15张1元。所以返回6。
arr=[3,5]，aim=2。任何方法都无法组成2元。所以返回0。
暴力递归思路
- 对于arr种某一面值，假设数组中第一个数据，如果不选中，那么求后面的所有面额组成aim的所有可能。
- 如果选中一张，aim减去这张面额，然后递归求解剩余面额解决剩余aim的问题
- 如果选中两张，aim就减去两张这样的面额，然后递归求解剩余面额解决剩余aim的问题。
- 如果选中三张总面额超出aim，则当前面额遍历结束，进入下一层
- 递归结束条件： 如果面额数组arr遍历结束了，且当前的aim==0,则返回1；
暴力递归代码
//+++++++++++++++++++++++++++++++++++方法一： 暴力递归的解法++++++++++++++++++++++++++++++++++++++++++++
public static int coins1(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
return process1(arr, 0, aim);
}
public static int process1(int[] arr, int index, int aim) {
int res = 0;
if (index == arr.length) {
res = aim == 0 ? 1 : 0;
} else {
for (int i = 0; arr[index] * i <= aim; i++) {
res += process1(arr, index + 1, aim - arr[index] * i);
}
}
return res;
}
暴力递归改动态规划
// +++++++++++++++++++++++++方法二： 改版暴力递归，从后往前遍历+++++++++++++++++++++++++++++++++++++++++++++
public static int coinsOther(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
return processOther(arr, arr.length - 1, aim);
}
public static int processOther(int[] arr, int index, int aim) {
int res = 0;
if (index == -1) {
res = aim == 0 ? 1 : 0;
} else {
for (int i = 0; arr[index] * i <= aim; i++) {
res += processOther(arr, index - 1, aim - arr[index] * i);
}
}
return res;
}
纸牌博弈问题
问题描述
【题目】
给定一个整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
【举例】
arr=[1,2,100,4]。开始时玩家A只能拿走1或4。如果玩家A拿走1，则排列变为[2,100,4]，接下来玩家B可以拿走2或4，然后继续轮到玩家A。如果开始时玩家A拿走4，则排列变为[1,2,100]，接下来玩家B可以拿走1或100,然后继续轮到玩家A。玩家A作为绝顶聪明的人不会先拿4，因为拿4之后，玩家B将拿走100。所以玩家A会先拿1，让排列变为[2,100,4]，接下来玩家B不管怎么选，100都会被玩家A拿走。玩家A会获胜，
分数为101。所以返回101。arr=[1,100,2]。开始时玩家A不管拿1还是2，玩家B作为绝顶聪明的人，都会把10拿走。玩家B会获胜，分数为100。所以返回100。
思路分析
- 首先两个玩家从一堆纸牌中抽出纸牌，他们只可能有两种情况，第一先抽，第二后抽。
- 那么直接计算出玩家先抽和后抽两种可能，就是暴力递归的求解思路
- 如果先抽，那么可以从数组两头选择一张，然后在剩下来的数组中后抽。
- 如果后抽，那么可以从已经抽完一张的数组两侧选择一张。
暴力递归代码如下
//++++++++++++++++++++++++++++++++暴力递归求解++++++++++++++++++++++++++++++++++++++
public static int win1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
// 先选的最大和后选的最大值中求出最大的结果
return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
}
// 先选的方法
public static int f(int[] arr, int i, int j) {
if (i == j) {
return arr[i];
}
// 可以先选i位置的元素，后选[i+1,j]位置上的元素
// 也可以先选j位置上的元素，然后后选[i,j-1]位置上的元素
return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
}
// 后选的方法
public static int s(int[] arr, int i, int j) {
// 如果数组中只有一个元素，而且是后选，那么肯定直接返回0
if (i == j) {
return 0;
}
return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
}
暴力递归改动态规划
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int[][] f = new int[arr.length][arr.length];
int[][] s = new int[arr.length][arr.length];
for (int j = 0; j < arr.length; j++) {
f[j][j] = arr[j];
for (int i = j - 1; i >= 0; i--) {
f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
}
}
return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
}
机器人路径问题
问题描述
指定一个机器人，可以在0 - n的线性网格中左右移动，如果机器人在0位置，只能向右移动，如果机器人在n位置，只能向左移动，否则可以选择向两边移动。
【问题】
现在给你网格长度n, 机器人初始位置m, 机器人可以移动的步数p, 求最终机器人落在k位置有多少种情况？
暴力递归思路
- 每一步，机器人可以选择向左移动也可以选择向右移动
- 如果越界则直接返回0
- 否则，计算向左移动的之后的路径总数和，和向右移动一步的路径总数和，构成暴力递归的思想。
暴力递归代码
//+++++++++++++++++++++++++++++++++---阿里笔试题----+++++++++++++++++++++++++++++++++++++++++
/**
* 问题描述：给定一个机器人，在0-n长度的格子中行走，起始位置为m,移动的步数为p
* 如果机器人在0位置，那么只能往右走
* 如果机器任在n位置，那么只能往左走
* 如果机器人在中间位置，那么即可以往左走也可以往右走
*
* 问： 机器任走p步，最终落在k位置有多少种移动的方式
* @param n
* @param m
* @param k
* @return
*/
public static int stepNums(int n, int m, int k, int p){
// 如果越界了，直接返回0
if(m > n || m < 0) return 0;
// 如果步数用完了，且当前机器人在k的位置，则返回1
if(p == 0) return k == m ? 1 : 0;
// 机器向左走的方式
return stepNums(n, m + 1, k, p - 1) + stepNums(n, m - 1, k, p - 1);
}
暴力递归改动态规划
//++++++++++++++++++++--------改动态规划---------++++++++++++++++++++
public static int stepNums2(int n, int m, int k, int p){
if(m > n || m < 0 || p < 1 || k < 0 || k > m){
return 0;
}
int[][] dp = new int[p+1][n+1];
for (int i = 0; i <= p; i++) {
for (int j = 0; j <= n; j++) {
if(i == 0){
dp[i][j] = j == m ? 1 : 0; // 出发点是m, 所以初始化m点的位置是1
}else if(j == 0){
dp[i][j] = dp[i-1][j+1];
}else if(j == n){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
}
}
}
return dp[p][k];
}
