{"action":"created","issue":{"url":"https://api.github.com/repos/honghaoz/CrackingTheCodingInterview/issues/6","repository_url":"https://api.github.com/repos/honghaoz/CrackingTheCodingInterview","labels_url":"https://api.github.com/repos/honghaoz/CrackingTheCodingInterview/issues/6/labels{/name}","comments_url":"https://api.github.com/repos/honghaoz/CrackingTheCodingInterview/issues/6/comments","events_url":"https://api.github.com/repos/honghaoz/CrackingTheCodingInterview/issues/6/events","html_url":"https://github.com/honghaoz/CrackingTheCodingInterview/issues/6","id":186978207,"number":6,"title":" Dynamic programming","user":{"login":"honghaoz","id":3926785,"avatar_url":"https://avatars.githubusercontent.com/u/3926785?v=3","gravatar_id":"","url":"https://api.github.com/users/honghaoz","html_url":"https://github.com/honghaoz","followers_url":"https://api.github.com/users/honghaoz/followers","following_url":"https://api.github.com/users/honghaoz/following{/other_user}","gists_url":"https://api.github.com/users/honghaoz/gists{/gist_id}","starred_url":"https://api.github.com/users/honghaoz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/honghaoz/subscriptions","organizations_url":"https://api.github.com/users/honghaoz/orgs","repos_url":"https://api.github.com/users/honghaoz/repos","events_url":"https://api.github.com/users/honghaoz/events{/privacy}","received_events_url":"https://api.github.com/users/honghaoz/received_events","type":"User","site_admin":false},"labels":[{"id":157294505,"url":"https://api.github.com/repos/honghaoz/CrackingTheCodingInterview/labels/Ongoing","name":"Ongoing","color":"84b6eb","default":false}],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":8,"created_at":"2016-11-03T04:46:27Z","updated_at":"2016-11-13T21:54:15Z","closed_at":"2016-11-03T04:48:33Z","body":"## Dynamic programming [6/16]\r\n| ❔ | Title | Difficulty | Time | Space |\r\n| -- | ----- | ---------- | ---- | ----- |\r\n❌ | [Nested List Weight Sum](https://leetcode.com/problems/nested-list-weight-sum/)| Easy| O(n)| O(1)|\r\n✅ | [Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)| Easy| O(n)| O(1)|\r\n✅ | [Unique Paths](https://leetcode.com/problems/unique-paths/)| Medium| O(mn)| O(mn)|\r\n✅ | [Unique Paths II](https://leetcode.com/problems/unique-paths-ii/)| Medium| O(mn)| O(mn)|\r\n✅ | [Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)| Medium| O(n^2)| O(n)|\r\n✅ | [Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)| Easy| O(n)| O(1)|\r\n✅ | [Coin Change](https://leetcode.com/problems/coin-change/)| Medium| O(n^2)| O(n)|\r\n❌ | [Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)| Medium| O(n^2)| O(n)|\r\n❌ | [Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)| Medium| O(n^2)| O(n^2)|\r\n❌ | [Perfect Squares](https://leetcode.com/problems/perfect-squares/)| Medium| O(n^2)| O(n)|\r\n❌ | [House Robber](https://leetcode.com/problems/house-robber/)| Easy| O(n)| O(1)|\r\n❌ | [House Robber II](https://leetcode.com/problems/house-robber-ii/)| Medium| O(n)| O(1)|\r\n❌ | [Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)| Medium| O(n)| O(1)|\r\n❌ | [Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/)| Medium| O(n)| O(1)|\r\n❌ | [Maximal Square](https://leetcode.com/problems/maximal-square/)| Medium| O(mn)| O(mn)|\r\n❌ | [Edit Distance](https://leetcode.com/problems/edit-distance/)| Hard| O(mn)| O(mn)|"},"comment":{"url":"https://api.github.com/repos/honghaoz/CrackingTheCodingInterview/issues/comments/260215752","html_url":"https://github.com/honghaoz/CrackingTheCodingInterview/issues/6#issuecomment-260215752","issue_url":"https://api.github.com/repos/honghaoz/CrackingTheCodingInterview/issues/6","id":260215752,"user":{"login":"honghaoz","id":3926785,"avatar_url":"https://avatars.githubusercontent.com/u/3926785?v=3","gravatar_id":"","url":"https://api.github.com/users/honghaoz","html_url":"https://github.com/honghaoz","followers_url":"https://api.github.com/users/honghaoz/followers","following_url":"https://api.github.com/users/honghaoz/following{/other_user}","gists_url":"https://api.github.com/users/honghaoz/gists{/gist_id}","starred_url":"https://api.github.com/users/honghaoz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/honghaoz/subscriptions","organizations_url":"https://api.github.com/users/honghaoz/orgs","repos_url":"https://api.github.com/users/honghaoz/repos","events_url":"https://api.github.com/users/honghaoz/events{/privacy}","received_events_url":"https://api.github.com/users/honghaoz/received_events","type":"User","site_admin":false},"created_at":"2016-11-13T21:54:15Z","updated_at":"2016-11-13T21:54:15Z","body":"## Longest Increasing Subsequence\r\n\r\n思路的关键就是找到state，找到transition function\r\n\r\n```swift\r\nclass Solution {\r\n    func lengthOfLIS(_ nums: [Int]) -> Int {\r\n        guard nums.count > 0 else { return 0 }\r\n        \r\n        var s = Array(repeating: 1, count: nums.count)\r\n        for i in 0..<nums.count {\r\n            for j in 0..<i {\r\n                if nums[i] > nums[j] && s[j] + 1 > s[i] {\r\n                    s[i] = s[j] + 1\r\n                }\r\n            }\r\n        }\r\n        return s.max()!\r\n    }\r\n}\r\n```"}}
{"actor":{"display_login":"honghaoz"}}