LeetCode Summary
  • Introduction
  • DP, 动态规划类
    • Best Time to Buy and Sell Stock III 题解
    • Best Time to Buy and Sell Stock 题解
    • Climbing Stairs 题解
    • Decode Ways 题解
    • Distinct Subsequences 题解
    • Edit Distance 题解
    • Interleaving String 题解
    • Longest Palindromic Substring 题解
    • Maximum Product Subarray 题解
    • Maximum Subarray 题解
    • Minimum Path Sum 题解
    • Palindrome Partitioning 题解
    • Palindrome Partitioning II 题解
    • Scramble String 题解
    • Triangle 题解
    • Unique Binary Search Trees 题解
    • Unique Paths II 题解
    • Word Break 题解
    • Word Break II 题解
  • list, 链表相关
    • Add Two Numbers 题解
    • Convert Sorted List to Binary Search Tree 题解
    • Copy List with Random Pointer 题解
    • Insertion Sort List 题解
    • LRU Cache 题解
    • Linked List Cycle 题解
    • Linked List Cycle II 题解
    • Merge Two Sorted Lists 题解
    • Merge k Sorted Lists 题解
    • Partition List 题解
    • Remove Duplicates from Sorted List 题解
    • Remove Duplicates from Sorted List II 题解
    • Remove Nth Node From End of List 题解
    • Reorder List 题解
    • Reverse Linked List II 题解
    • Reverse Nodes in k-Group 题解
    • Rotate List 题解
    • Sort List 题解
    • Swap Nodes in Pairs 题解
  • binary tree, 二叉树相关
    • Balanced Binary Tree 题解
    • Binary Tree Inorder Traversal 题解
    • Binary Tree Level Order Traversal 题解
    • Binary Tree Level Order Traversal II 题解
    • Binary Tree Maximum Path Sum 题解
    • Binary Tree Postorder Traversal 题解
    • Binary Tree Preorder Traversal 题解
    • Binary Tree Zigzag Level Order Traversal 题解
    • Construct Binary Tree from Inorder and Postorder Traversal 题解
    • Construct Binary Tree from Preorder and Inorder Traversal 题解
    • Convert Sorted List to Binary Search Tree 题解
    • Flatten Binary Tree to Linked List 题解
    • Maximum Depth of Binary Tree 题解
    • Minimum Depth of Binary Tree 题解
    • Path Sum 题解
    • Path Sum II 题解
    • Populating Next Right Pointers in Each Node 题解
    • Populating Next Right Pointers in Each Node II 题解
    • Recover Binary Search Tree 题解
    • Same Tree 题解
    • Sum Root to Leaf Numbers 题解
    • Symmetric Tree 题解
    • Unique Binary Search Trees 题解
    • Unique Binary Search Trees II 题解
    • Validate Binary Search Tree 题解
  • sort, 排序相关
    • 3Sum Closest 题解
    • 3Sum 题解
    • 4Sum 题解
    • Insert Interval 题解
    • Longest Consecutive Sequence 题解
    • Merge Intervals 题解
    • Merge Sorted Array 题解
    • Remove Duplicates from Sorted Array 题解
    • Remove Duplicates from Sorted Array II 题解
    • Sort Colors 题解
    • Two Sum 题解
  • search, 搜索相关
    • First Missing Positive 题解
    • Find Minimum in Rotated Sorted Array 题解
    • Find Minimum in Rotated Sorted Array II 题解
    • Median of Two Sorted Arrays 题解
    • Search Insert Position 题解
    • Search a 2D Matrix 题解
    • Search for a Range 题解
    • Search in Rotated Sorted Array 题解
    • Search in Rotated Sorted Array II 题解
    • Single Number 题解
    • Single Number II 题解
  • math, 数学类相关
    • Add Binary 题解
    • Add Two Numbers 题解
    • Divide Two Integers 题解
    • Gray Code 题解
    • Integer to Roman 题解
    • Multiply Strings 题解
    • Palindrome Number 题解
    • Plus One 题解
    • [Pow(x, n) 题解](math/Pow(x,-n).md)
    • Reverse Integer 题解
    • Roman to Integer 题解
    • [Sqrt(x) 题解](math/Sqrt(x).md)
    • [String to Integer (atoi) 题解](math/String-to-Integer-(atoi).md)
    • Valid Number 题解
  • string, 字符串处理相关
    • Anagrams 题解
    • Count and Say 题解
    • Evaluate Reverse Polish Notation 题解
    • [Implement strStr() 题解](string/Implement-strStr().md)
    • Length of Last Word 题解
    • Longest Common Prefix 题解
    • Longest Palindromic Substring 题解
    • Longest Substring Without Repeating Characters 题解
    • Longest Valid Parentheses 题解
    • Minimum Window Substring 题解
    • Regular Expression Matching 题解
    • Reverse Words in a String 题解
    • Simplify Path 题解
    • Text Justification 题解
    • Valid Parentheses 题解
    • Wildcard Matching 题解
    • ZigZag Conversion 题解
  • combination and permutation, 排列组合相关
    • Combinations 题解
    • Combination Sum 题解
    • Combination Sum II 题解
    • Letter Combinations of a Phone Number 题解
    • Next Permutation 题解
    • Palindrome Partitioning 题解
    • Permutation Sequence 题解
    • Permutations 题解
    • Permutations II 题解
    • Subsets 题解
    • Subsets II 题解
    • Unique Paths 题解
  • matrix, 二维数组, 矩阵相关
    • Rotate Image 题解
    • Set Matrix Zeroes 题解
    • Spiral Matrix 题解
    • Spiral Matrix II 题解
    • Maximal Rectangle 题解
  • 回溯, BFS/DFS
    • Clone Graph 题解
    • Generate Parentheses 题解
    • N-Queens 题解
    • N-Queens II 题解
    • Restore IP Addresses 题解
    • Sudoku Solver 题解
    • Surrounded Regions 题解
    • Word Ladder 题解
    • Word Ladder II 题解
    • Word Search 题解
  • greedy, 贪心
    • Best Time to Buy and Sell Stock II 题解
    • Jump Game 题解
    • Jump Game II 题解
  • 其他
    • Candy 题解
    • Container With Most Water 题解
    • Gas Station 题解
    • Gray Code 题解
    • Max Points on a Line 题解
    • [Pascal's Triangle 题解](others/Pascal's-Triangle.md)
    • [Pascal's Triangle II 题解](others/Pascal's-Triangle-II.md)
    • Remove Element 题解
    • Trapping Rain Water 题解
Powered by GitBook
On this page

Was this helpful?

  1. DP, 动态规划类

Unique Paths II 题解

PreviousUnique Binary Search Trees 题解NextWord Break 题解

Last updated 5 years ago

Was this helpful?

题目来源：

> Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the middle of a 3x3 grid as illustrated below. [ [0,0,0], [0,1,0], [0,0,0] ] The total number of unique paths is 2. Note: m and n will be at most 100.

解题思路： 跟 差不多. 这里就省却递归方法了，直接用DP。

    int uniquePathsWithObstacles(vector<vector<int> > &grid) 
    {
        int m = grid.size(); if (m == 0) return 0;
        int n = grid[0].size();
        if(grid[0][0] == 1) return 0;
        vector<vector<int> > dp(m, vector<int>(n, 0));
        for(int i = 0; i < n; i++)
        {
            if(grid[0][i] == 1)
                break;
            dp[0][i] = 1;
        }
        for(int i = 0; i < m; i++)
        {
            if(grid[i][0] == 1)
                break;
            dp[i][0] = 1;
        }
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
            {
                if(grid[i][j] == 1)
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
           }
        return dp[m-1][n-1];
    }
Unique Paths II
minimum-path-sum