我刚刚开始学习dp,并尝试使用相同的(https://leetcode.com/problems/unique-paths/)
机器人位于m x n网格的左上角(下图中标记为“开始”)。
机器人只能在任何时间点向下或向右移动。机器人正试图到达网格的右下角(在下图中标记为“完成”)。
有多少可能的唯一路径?
以下是我尝试的:
public class Solution {
public int uniquePaths(int m, int n) {
int [][] grid = new int[m][n];
int [][] memo = new int[m][n];
return uniquePathsHelper(grid,m,n,memo);
}
public int uniquePathsHelper(int [][] grid, int row,int col,int[][]memo){
if(row>grid.length-1 || col>grid[0].length-1) return -1;
if(row == grid.length-1 && col == grid[0].length-1) return 0;
if(memo[row][col]!=0) return memo[row][col];
if(col == grid[0].length-1) memo[row][col] = uniquePathsHelper(grid,row+1,col,memo)+1;
if(row == grid.length-1) memo[row][col] = uniquePathsHelper(grid,row,col+1,memo)+1;
// int rowInc = Integer.MIN_VALUE;
// int colInc = Integer.MIN_VALUE;
// if(row<grid.length-1) rowInc = uniquePathsHelper(grid, row+1,col,memo);
// if(col<grid.length-1) colInc = uniquePathsHelper(grid,row,col+1,memo);
// if(row == grid.length-1 || col == grid[0].length-1) return 1;
// if(row<grid.length-1) return 2;
// if(col<grid[0].length-1) return 2;
if(col< grid[0].length-1 && row < grid.length-1) memo[row][col] = memo[row+1][col] + memo[row][col+1];
System.out.println("Memo["+row+"]["+col+"] = "+memo[row][col]);
return memo[0][0];
}
}
抱歉,如果这听起来很基本,我知道我遗漏了一些东西。有人能指出它有什么问题吗?
为了解决这个问题,让我们为f(r, c)
定义一个循环公式。可能有几个选项可以做到这一点,但让我们坚持使用代码中的内容。
f(r,c)=0如果r
根据公式,
uniquePathsHelper
会是什么样子?
// actually we don't need grid at all.
// assume that we have m rows and n cols, m and n are global variables
public int uniquePathsHelper(int row, int col, int[][] memo) {
// 1-st and 2-d formulas
if(row >= m || col >= n) return 0;
// 3-d formula
if(row == m - 1 && col == n - 1) return 1;
if(memo[row][col] != 0) {
// 4-th formula
memo[row][col] = uniquePathsHelper(row, col + 1, memo) +
uniquePathsHelper(row + 1, col, memo);
}
return memo[row][col];
}
要接收答案,只需调用
uniquePathsHelper(0,0, memo)
,这意味着从(0,0)-cell到(m-1, n-1)-cell存在多少条路径?
我正在尝试实施这个问题的解决方案,但我遇到了一些问题。 问题是: “在r行和c列的网格的左上角有一个机器人。机器人只能向右或向下移动,某些单元格是“禁止”的,这意味着机器人不能踩它们。设计一个算法来为机器人找到从左上角到右下的路径。” 解决方案如下所示: 让我困惑的是动态编程的尝试。 从不计算为。 我已经覆盖了Point类中的和方法,所以失败了。只要所比较的对象具有相同的行和列值,contains
我有一个子集问题的工作代码,如果它发现一个子集等于所需的目标,它可以打印数字。 > 我想打印给定目标的所有可能的子集,我不知道要为此更改什么。 我如何让它对负数起作用?
动态规划(Dynamic programming,简称 DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出
给定一个数组,是否可以从起始索引开始选择一组整数,这样该组就与给定的目标相加?但是,附加的限制是必须选择所有的6。 groupSum6(0,[5,6,2],8)true groupSum6(0,[5,6,2],9)false groupSum6(0,[5,6,2],7)false 只是想弄清楚我错在哪里。声明nums[start]==6的特殊情况是不是错误的方法?
我正在为动态编程编写一些复习材料。我需要提出如何划分子问题,计算出基本情况,并提出递归公式。 给定 n 个正整数 a1,a2,...,an、一个数字 k 和一个目标 W,我们希望选择一个子集 T,其总和恰好是 k 个元素,其总和最接近 W。每个元素只能选择一次。定义一个具有 3 个参数的子问题(即 C[x,y,z] = ...)。 我只处理过几个动态编程示例,从未处理过定义子问题时需要3个参数的示
斐波那契数列 1. 爬楼梯 2. 强盗抢劫 3. 强盗在环形街区抢劫 4. 信件错排 5. 母牛生产 矩阵路径 1. 矩阵的最小路径和 2. 矩阵的总路径数 数组区间 1. 数组区间和 2. 数组中等差递增子区间的个数 分割整数 1. 分割整数的最大乘积 2. 按平方数来分割整数 3. 分割整数构成字母字符串 最长递增子序列 1. 最长递增子序列 2. 一组整数对能够构成的最长链 3. 最长摆动子