唯一路径的动态规划解法，阿里巴巴架构演化路径 John 易筋 ARTS 打卡 Week 07

关注

发布于: 2020 年 07 月 04 日

1. Algorithm: 每周至少做一个 LeetCode 的算法题62. Unique Paths
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
﻿
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
﻿
How many possible unique paths are there?
﻿
﻿
Above is a 7 x 3 grid. How many possible unique paths are there?
﻿
Example 1:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
﻿
Example 2:
Input: m = 7, n = 3
Output: 28
﻿
Constraints:
﻿
1 <= m, n <= 100
It's guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.
﻿
1 动态规划解法动态规划主要是找到跟上一条记录联系的公式，这里的公式就是path[i][j] = path[i-1][j] + path[i][j-1]。可以看下面的图，
往下走的列path[i][0]都初始化为1，表示一直往下有一种的解法；往右走的行path[0][j]都初始化为1，表示一直往右有一种的解法。
再看第二列，当前位置的记录是由上面的解法，和左边的解法，加起来就是当前的解法。所以 2 = 1 + 1， 3 = 2 + 1. 以此类推。
结果是path[m-1][n-1], 因为是从0开始计算的。
﻿
﻿
public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0 ; i < m; i++) {
      dp[i][0] = 1;
    }
    for (int k = 0; k < n; k++) {
      dp[0][k] = 1;
    }
    for (int i = 1; i < m; i++) {
      for (int k = 1; k < n; k++) {
        dp[i][k] = dp[i - 1][k] + dp[i][k - 1];
      }
    }
﻿
    return dp[m - 1][n - 1];
  }
﻿
2 二项系数解法Binomial coefficient数学公式的解法，实际上先考虑一共要走多少步。比如Input: m = 7, n = 3，实际上是 m- 1 + n -1, 也就是8步。这就是表示有8个空要等着填。那么有多少种填发呢，比如往下走表示D，往右走表示R，因为二项系数解法，大小都是一样的，为了效率，用小的来解比较快。比如有2个R, 由于 (n - 1)。那么第一个R可以放任意8个位置中的一个，第二个R可以放任意7个位置中的一个。因为左边(1, 2)和 (2, 1)，都是放R的话是一样的，所以就要除以二项系数的当前系数。
﻿
﻿
class Solution {
    public int uniquePaths(int m, int n) {
        int totalStep = m + n - 2;
        int change = (m > n ? n : m) - 1;
        double count = 1;
        for (int i = 1; i <= change; i++) {
          count = count * totalStep / i;
          totalStep--;
        }
        return (int)count;
    }
}
﻿
2. Review: 阅读并点评至少一篇英文技术文章看了iOS开源项目趋势，基本上都是SwiftUI、ARKit相关，依然没什么大的看点。
﻿
Top 10 Trending iOS Projects at the Start of 2020https://medium.com/better-programming/top-10-trending-ios-projects-at-the-start-of-2020-62dfff1707e0
﻿
3. Tips: 学习至少一个技术技巧博客：什么是运行时应用程序自我保护（RASP）Runtime Application Self-Protection
﻿
在企业中部署的应用程序位于由网络，操作系统和数据库组成的复杂且分散的环境中。这通常会导致应用程序的安全体系结构分散，再加上缺乏精确且可靠的安全路线图。运行时应用程序自我保护（RASP）的概念已得到很大发展，以解决开发人员面对威胁时采用的即席方法。
﻿
最新数据表明，有38％的iOS移动应用程序和43％的Android移动应用程序带有高风险漏洞。由于安全架构的弱点，其中很大一部分（针对iOS的74％和针对Android的57％）会影响移动应用程序。不安全的进程间通信也是38％的Android应用程序和22％的iOS应用程序中发现的漏洞。
开发人员没有解决应用程序中的设计缺陷，而是倾向于采用静态和传统的AppSec方法，这些方法通常会因复杂的安全威胁而失败。这种分散的安全控制层通常成为应用程序，基础结构和安全层上多个组件的瓶颈，但是随着RASP解决方案的到来，应用程序安全性不再是对威胁的随意反应。
﻿
什么是RASP？
运行时应用程序自我保护（RASP）是应用程序安全生态系统中的一项创新，可通过提供对隐藏漏洞的更多可见性来处理对软件应用程序层的运行时攻击。它本质上是一种安全软件，可与应用程序或其运行时环境集成在一起，并不断拦截对应用程序的调用以检查其安全性。RASP软件无需等待威胁影响应用程序。相反，它会主动在进入应用程序的流量中寻找恶意软件，并防止在应用程序内部执行欺诈性呼叫。 
﻿
通过留在应用程序中，RASP解决方案消除了已知漏洞，并保护了应用程序免受未知的零日攻击，而无需任何人工干预。因此，与传统的安全方法（如Web应用程序防火墙（WAF））相比，RASP提供了与概念上不同的安全性范式，后者仅通过阻止所有可疑流量来保护应用程序。 
﻿
4. Share: 分享一篇有观点和思考的技术文章极客大学架构师训练营 系统架构 第7课 听课总结
﻿
说明
系统架构演进
﻿
讲师：李智慧
﻿
系统架构概述
互联网系统面临怎样的挑战？
﻿
20年前的系统架构主要是面对大型企业：IBM、SUN、Microsoft、Oracle、沃尔玛、家乐福、用友、金蝶、联想等。
最近这10几年主要是互联网的系统：Google、AWS、Facebook、阿里巴巴、腾讯等。
﻿
互联网系统面临挑战：高并发、大流量
Google 日均 PV 数 35 亿，日均 IP 访问数 3 亿。
微信在线用户数10亿。
天猫双十一活动一天交易额 3000 亿。
高并发是系统的需求，面临的问题；高性能、高可用是追求的目标。
﻿
高可用
系统 7x24 小时不间断服务。大型互联网网站的宕机事件通常会成为新闻焦点。
﻿
服务器升级，要可用。
数据迁移，要可用。
超过服务器接收能力(比如系统设计可接收用户为100w，来了1个亿用户)，要可用。
﻿
海量数据
需要存储、管理海量数据。
﻿
Facebook 每周上传的照片数目接近10亿。
Google 有近百万台服务器为全球用户提供服务。
百度收录的网页数目有数百亿。
用户分布广泛，网络情况复杂
许多大型互联网都是为全球用户提供服务的，用户分布范围广，各地网络情况千差万别。在国内，有各个运营商网络互通难的问题。而中美光缆的数次故障，也让一些对国外用户依赖较大的网站不得不考虑在海外建立数据中心。
﻿
安全环境恶劣
由于互联网的开放性，使得互联网网站更容易受到攻击，大型网站几乎每天都会遇到黑客攻击情况。2011年国内多个重要网站泄漏用户密码，让普通用户也直面一次互联网安全问题。
﻿
需求快速变更，发布频繁
和传统软件的版本发布频率不同，互联网产品为快速适应市场，满足用户需求，其产品发布频率也是极高的。Office 的产品版本以年为单位发布，而一般大型网站的产品每周都有新版本发布上线，至于中小型网站的发布就更频繁了，有时候一天会发布几十次。
﻿
渐进式发展
不同于传统软件产品或者企业应用系统，一开始就规划好全部的功能和非功能需求，几乎所有的大型互联网网站都是从一个小网站开始，渐进的发展起来的。
﻿
Facebook 是扎克伯格同学在哈佛大学的宿舍里开发的；
Google 的第一台服务器部署在斯坦福大学的实验室里；
阿里巴巴则是在马云家的客厅里诞生的。
好的互联网产品都是慢慢运营出来的，不是一开始就开发好的。那些刚建立就投入巨资，有巨大背景的网站，后来发展都很惨淡。
﻿
参考https://www.youtube.com/watch?v=M8BYckxI8_U
https://leetcode.com/problems/unique-paths/
﻿